A solução é simples mas inimaginavel...
Editar o arquivo a seguir:
sudo gedit /var/lib/NetworkManager/NetworkManager.state
Colocando: NetworkingEnabled=true
Aproveitando coloquei managed=true no arquivo por outro "possível" problema.
sudo gedit /etc/NetworkManager/nm-system-settings.conf