In my case this was I believe caused by avahi lookups taking priority.
In nsswitch.conf I had:
hosts: files mdns4_minimal [NOTFOUND=return] dns mdns4
I changed this to:
hosts: files dns mdns4_minimal [NOTFOUND=return] dns mdns4
and all was well.
My contribution to the increasing entropy and eventual heat death of the universe