For the last few weeks, I've noticed that no matter what computer I'm on, whether at work, home, or some random computer at a friend's house, or at the library, when I try to connect to any website for the first time that session, the "looking up/for www.example.com" at the bottom left of my browser window takes no less than four full seconds, but usually more like thirty seconds.
That's really slow for DNS resolution.
Like I say, I've noticed it on every computer I've tried here in Los Angeles.
Once the DNS resolves, the connection is plenty fast, and browsing speed is normal compared to what I'm used to experiencing.

Originally, I thought it was just my home computer, but then I noticed my work computers, all of them, were doing the same thing, and then I started paying attention, and noticed it happening on all computers I tried it on.

Has anyone else noticed this slowing down of the DNS layer?

There was recently found a flaw in the design of DNS (http://securosis.com/2008/07/08/dan-kaminsky-discovers-fundamental-issue-in-dns-massive-multivendor-patch-released/). More accurately, DNS was designed back in the day when there were no "bad guys" on the web.

On July 8, vendors for all DNS-related projects released patches to work around this vulnerability. The basic result is that ports are randomized instead of always using port 53. My guess is that this randomizing may take some more time than using a fixed port.

For a DNS provider that has been using source-port randomization all along, check out OpenDNS (http://opendns.org/). I've been using them for several years now, and it works great for me. Perhaps your current DNS provider is slow.

Good Luck,
WallyH