Comment 75 for bug 417757

The solution is to use a working DNS server.

A couple of ways to accomplish this:
 - use your ISP DNS servers directly
 - use OpenDNS or a similar provider
 - local caching resolver: put as the nameserver (/etc/resolv.conf) and install pdns-recursor

The latter can be done per default in Ubuntu and would always work and require no setting changes.
The only negative side-effect is that the caching effect of DNS might be less used, but then again, most sites use DNS loadbalancing now, thus this is a non-issue.