Comment 149 for bug 417757

WORKING FIX (run as root of course):

apt-get install pdns-recursor resolvconf
echo "nameserver" >> /etc/resolvconf/resolv.conf.d/base
resolvconf -u

1) This will effectively install pdns_recursor which is a DNS recursor that simply works(tm) and it installs the resolvconf framework (which you most likely already have)
2) this echo sets the nameserver to, aka pdns
3) update resolv.conf with the above info

You should now have "nameserver" in /etc/resolv.conf and all your DNS queries should be super duper fast again (also because they get locally cached a bit ;)

Of course if you have a firewall between your host and the Internet where DNS servers exist the above might not work when DNS gets blocked...

I would almost suggest that Ubuntu make the above the default. The problem is though that little firewall thing, if that is there or you visit some netcafe or other network where only HTTP/HTTPS works, then indeed it does not work...