As soluções do forum não deram certo, pelo menos as que eu tentei...
Achei uma outra solução...
A culpa deste erro do Network Manager é causada pelo conflito depois de upgrades. Para arrumar (ao menos provisoriamente), basta fazer um download da versão mais simples (downgrade) e instalar os mesmos nesta versão mais antiga. Eu resolvi seguindo estes passos
http://askubuntu.com/questions/727127/last-upgrade-crashes-network-manager-no-internet-connection-no-appletVeja no Step 2 que precisa fazer o download destes 3 pacotes. Em seguida, no terminal, colocar
sudo dpkg -i libnl-*.deb
e ai ele vai avisar que estara fazendo downgrade, pedir pra confirmar. Dando o ok, basta
sudo service network-manager restart
ou se este comando não der, como foi meu caso, fazer
sudo service network-manager stop
e em seguida
sudo service network-manager start
Ai bingo, ele conecta e tudo fica ok