Ihr Problem wird auf http://udrepper.livejournal.com/20948.html beschrieben und wird durch eine parallele Suche auf IPv4 und IPv6 verursacht, die mit einigen DNS-Servern und Firewalls nicht zusammenarbeitet.
Es kann behoben werden, indem "single-request" zu den Optionen in /etc/resolv.conf hinzugefügt wird, wie der Link oben erwähnt.