Sistema > Preferências > Conexões de Rede > Editar > Configurações IPx4 > Servidores DNS. O que quer que seja colocado lá, não funciona, talvez porque o seu ISP começou a bloquear o tráfego de DNS externo. Tente colocar lá os endereços dos servidores de nomes do OpenDNS, isto é "208.67.222.222, 208.67.220.220" sem as aspas.
Isso ajuda?
Outra opção é que o daemon avahi parou de funcionar