Remova os seguintes pacotes: network-manager-gnome
Instale os seguintes pacotes: python-wicd wicd wicd-daemon wicd-gtk
Fonte: http://ubuntuforums.org/showthread.php?t=1866335
Se isso funcionar para você, por favor vote / marque como aceito. Se não comentar, tentaremos ajudar ainda mais.