I was experiencing very slow dns resolving on Debian Squeeze. This was very noticeable when connecting with SSH. I took about 15 seconds before the password prompt showed up.
Pinging and digs worked fine. I checked lots of things, did some googling until I decided to step back a bit and check if the problem was related to the version of tcp/ip used.
Turned out to be the case. The first line in my resolv.conf was an ipv6 dns server which wasn’t responding to the requests.
Changed the dns server, problem solved.