It sounds like the same problem that I've had with verizon (flaky dns servers). Treewalk comes highly recommended from the dsl reports verizon forums. I am using this and I can say that it helps when you are able to connect to the internet but can't resolve the site name to the site address.
http://treewalkdns.com/