Tente desativar o IPv6. Algumas pessoas relatam ter problemas de DNS quando o suporte IPv6 está ativado. Você pode tentar desabilitá-lo para ver se isso faz alguma diferença no seu caso.
Você deve ser capaz de desabilitar o IPv6 adicionando ipv6.disable=1
aos parâmetros de inicialização do kernel (editando a configuração do Grub em /boot/grub/menu.lst
e executando sudo update-grub
conforme instruído, por exemplo aqui ).