Eu tive um problema semelhante e instalei o WICD. No terminal, insira esses comandos e sua senha.
sudo apt-get install wicd
sudo service network-manager stop
sudo killall wpa_supplicant
Isso instala o WICD e interrompe temporariamente o gerenciador de rede. Trabalhei para mim, não posso lhe dar muita ajuda além disso, no entanto.
Se funcionar, você pode prosseguir e limpar o gerenciador de rede (excluir NM e suas dependências)
sudo apt-get remove --purge network-manager network-manager-gnome