Eu me deparei com alguns problemas semelhantes recentemente com o Fedora 11 também. Você terá que traduzir o seguinte para o Ubuntu.
Descobri que reiniciar o processo do daemon do NetworkManager (em vez do applet) às vezes ajuda. Eu também tentei reiniciar o daemon HAL; mas acho que isso causou problemas devido a um rótulo do SELinux estar errado. (Tive que fazer restorecon -v nm-dhclient-eth0.conf
em /var/run
em algum momento depois dessa tentativa).
Atualmente executando o kernel 2.6.30.8-64.fc11.i686.PAE.