Tente reinstalar seu gerenciador de rede:
sudo apt-get purge network-manager*
sudo apt-get update
sudo apt-get install network-manager network-manager-gnome network-manager-pptp network-manager-pptp-gnome
Os comandos acima são para Unity / Gnome. Outros desktops exigirão pacotes diferentes.