Estou em 14.04 LTS, mas tive o mesmo problema e descobri que minhas pesquisas de DNS estavam de alguma forma olhando para o lugar errado (localmente).
No NetworkManager ( nm-connection-editor ), meu servidor DNS foi definido como 192.168.100.1 . Mas quando a verificação de /etc/resolv.conf me diz 127.0.1.1 . Então, se eu tentar procurar algo:
$ nslookup www.google.com
Server: 127.0.1.1
...
Depois de remover o dns=dnsmas -row de /etc/NetworkManager/NetworkManager.conf e reiniciar, ele funciona perfeitamente. /etc/resolv.conf diz-me 192.168.100.1 e primeira linha de nslookup :
$ nslookup www.google.com
Server: 192.168.100.1
...