Eu tive um problema semelhante. Um atalho para que funcione novamente é usar o Wicd - link - que é uma alternativa ao gerenciador de rede.
A outra maneira é restaurar o gerenciador de rede do repositório novamente. Execute sudo make uninstall
e exclua quaisquer bibliotecas do gerenciador de rede, apt-get --purge remove network-manager
(e quaisquer outros pacotes), e reinstale todos os pacotes e o gnome-networkmanager.
Além disso, a execução do applet nm a partir do terminal pode gerar algumas informações de depuração mais úteis - identificando principalmente se o applet poderia criar uma conexão d-bus com o gerenciador de rede.