Estou trabalhando com o Ubuntu Mate 16.04 e o mesmo problema. Este é um bug, e você pode continuar executando
sudo service network-manager restart
Esperando que este bug seja corrigido, escrevi a linha
service network-manager restart
(sem sudo) no meu arquivo /etc/rc.local
.
Desta forma, o comando é iniciado cada vez que eu inicio a minha sessão ... Para modificar o arquivo, podemos editar com algo como
sudo gedit /etc/rc.local
Espero que o gerente de rede seja atualizado em breve.