O que um teste de velocidade de algum lugar como speakeast.net diz? Os resultados são consistentes?
EDIT 1: Se você acha que é DNS, abra o terminal e digite: dig www.google.com
(substituindo www.google.com pelo nome do host a verificar. Quando os resultados forem exibidos, procure a linha: Query time: ** msec
. a saída?
EDIT 2: Como o DNS não parece ser o problema, como o HTTP bruto parece funcionar? No terminal, tente:
HOST=www.google.com
time echo -e "GET / HTTP/1.1\nHOST: $HOST\n\n"|nc $HOST 80
e vamos ver quanto tempo demora. (Obviamente basta alterar HOST = para o nome do host para verificar)
FINAL EDIT : para outras pessoas com o mesmo problema, consulte os comentários. A questão acabou por ser servidores DNS errados listados na configuração de rede.