Es normal si hace menos de 3 días que has cambiado los DNS. Nosotros hemos tenido experiencias similares con algunos clientes, curiosamente la mayoría usaba Wanadoo como proveedor de acceso a Internet, parece que tienen sus DNS un poco "descontrolados".
Sobre el proxy de Telefónica hay bastante información en Internet:
http://www.google.es/search?hl=es&q=...3%B3nica&meta=
Y métodos para evitarlos, aunque no los he probado personalmente...