Também encontrei isso com upgrade para 16.04 a partir de 14.04.
Eu olhei no launch pad e encontrei um bug aberto que eu acho que combina:
A solução final parece ser remover o arquivo:
/run/resolvconf/interface/NetworkManager
Eu não posso confirmar a solução alternativa, pois desde que encontrei esse segmento, atualizei com apt-get upgrade
e reinicializei e o problema está ausente para mim.
Esse arquivo
/run/resolvconf/interface/NetworkManager
também está ausente agora.
Acho que esta é a solução (para 16.04) e a solução alternativa para 14.04.