Tivemos o mesmo problema e descobrimos que nosso hardware apresentava um comportamento inoperante com o IPv6.
Você pode verificar novamente com curl
e forçar o IPv4 da seguinte forma:
$ time curl -4 www.google.com
...
real 0m0.074s
user 0m0.011s
sys 0m0.000s
Atualização 1:
Tivemos o problema com o nosso Sistema de Host do Windows (o Ubuntu 14.04 é o convidado). A solução atual foi encontrada em esta página.
Adicionar options single-request-reopen
ao /etc/resolvconf/resolv.conf.d/base
e executar sudo resolvconf -h
foi o suficiente para nós.
Eu encontrei outra resposta no askubuntu que sugeriu quase o mesmo.