Autonegotiate sometimes does that - and with most consumer kit (like Xboxes) and most domestic network switches you can't turn it off. Essentially the 802.3u protocol isn't very robust, and can fail in strange ways. The most common is duplex mismatch, but it's not the only one. There's very little you can do about it - a better quality cable sometimes helps, as does plugging into another port on the same device (yes, it can be that fragile!), or cleaning the connection - as you discovered. The most common cause is electrical noise or other signal degradation, or a component that is at one end of its allowed tolerance band.
Bottom line is that sometimes plug and play networking just doesn't work!
Now, having said that, you might still have a dodgy network interface in the Xbox....
You could try having a look at the network status in UnleashX or XBMC, see if it changes when you are having problems.