Verifique se você tem
dns=dnsmasq
em /etc/NetworkManager/NetworkManager.conf
. Se fizer isso, tente comentá-lo e reinicie o gerenciador de rede:
sudo service network-manager restart
Verifique também se /etc/resolv.conf
é um link simbólico para /run/resolvconf/resolv.conf