同じような情報ですが。
http://lists.openwall.net/netdev/2011/12/18/7

mii-toolでもautonegoをoffにできるようです。
http://manpages.ubuntu.com/manpages/gutsy/ja/man8/mii-tool.8.html

うーん。なんでしょうね。
元々の本質的な問題の前に、何か別のおかしな現象にあたってしまっているようにも思えますが。。
最初の投稿に/etc/sysctl.confを編集したとありましたが、/etc/network/interfacesも初期の状態から変わっていたようですし、何か他に変更している部分はないでしょうか。まずは、変更した部分を元に戻すところから始めた方がよいかも知れませんね。
もし、加えた変更を記録/記憶していないということがあれば、インストールしなおすことも考えた方が良いかもです。