a mesma coisa acontecendo aqui eu acho que é algo relacionado ao DNSMASQ algumas vezes a resolução dns nunca funciona, algumas vezes ele trabalha devagar levando para cada nome cerca de 3 segundos para resolver, e às vezes roda muito rápido como deveria ser. Estou executando o Ubuntu 15.10 e sim, eu tentei mudar os servidores dns para o meu provedor, Goolge, e não parece nada estável
UPDATE: acho que encontrei a solução
SOLUÇÃO
O problema parece estar relacionado aos pacotes dnsmasq e resolvconf conflitantes. Até 12.10, o dnsmasq foi usado. A partir de 13.04, o Ubuntu pareceu mudar para um híbrido dnsmasq / resolvconf, onde você instalou os pacotes dnsmasq-base e resolvconf, mas não o próprio dnsmasq.
Não sei se é um bug nos scripts de atualização do 13.04 ou qualquer outra coisa, porque ao atualizar (como em novas instalações) o resolvconf é instalado, o dnsmasq-base é atualizado e o dnsmasq é (corretamente) desinstalado.
O problema é que o script de upgrade não consegue comentar a linha dns = dnsmasq em /etc/NetworkManager/NetworkManager.conf. Então, mesmo que o daemon dnsmasq não esteja mais presente no sistema, o /etc/resolv.conf ainda espera que seja.
SO para corrigir o problema edite este arquivo /etc/NetworkManager/NetworkManager.conf e comente esta linha: # dns = dnsmasq
espero que isso ajude alguém