Tente a resposta postada por varunendra
% bl0ck_qu0te%sudo apt-get install -d --reinstall network-manager network-manager-gnome
Em seguida, limpe-o
sudo apt-get purge network-manager-gnome network-manager
% bl0ck_qu0te%
sudo apt-get install network-manager-gnome