Linux e internet

[living]

Hola a todos. He probado ya varias distribuciones (mandriva 2006, Fedora y ahora ubuntu) y en todas me he encontrado el mismo problema. Cuando abro un navegador (da igual que sea Opera, Konqueror o firefox) y pongo una dirección (o pincho en un link de google) tarda mucho en cargar la página. Se queda pensando un rato y después si que "suelta" la página rápido. Como después navegando por el site no tengo ese problema he pensado que el problema está en las DNS, en cuanto saca la ip de la dirección, la navegación es rápida. Tengo las misma DNS que en windows y en este último no tengo esos problemas. Hay alguna solución para eso??. Muchas gracias por adelantado.