Já tentou reinstalar o NetworkManager? Se você puder se conectar via ethernet - porque, naturalmente, a remoção do NetworkManager desconectaria você - tente:
sudo apt-get -y purge network-manager
sudo apt-get -y install network-manager
Eu tive problemas com o NetworkManager no passado e, portanto, uso o wicd na maioria das vezes. No entanto, ele não tem certos recursos, como gerenciar várias interfaces por vez e criar redes ad-hoc, etc., então eu uso o NetworkManager quando preciso, mas, por outro lado, uso o wicd.
Editar: Se isso não funcionar, tente o método CLI conforme descrito aqui: link