Quais servidores DNS você está usando? Abra "Configurações do Sistema" e vá para "Rede". Você pode alterar os servidores DNS de lá. Seu ISP deve ter servidores que você possa usar, mas você também pode tentar outra coisa. Eu sei que o Google tem dois servidores em 8.8.8.8
e 8.8.4.4
que funcionam para mim.
Para depurar problemas de DNS, você pode usar escavação e ping. Experimente estes comandos:
dig <some-domain.com>
ping <DNS-server-IP-address>
Os valores podem ser, por exemplo:
dig ubuntu.com
ping 8.8.8.8
Se a alteração dos servidores DNS não funcionar, poste a saída dos comandos acima aqui.