It seems that Ubuntu/Debian (or perhaps other distros as well) prefer IPv6 DNS records instead of IPv4 when applicable and some times this results in loss of connectivity or similar problems.
I ran into this issue today while trying to update an old VPS with apt-get/aptitude. Specifically, was being resolved in an unreachable IPv6 address and I had to wait some minutes for timeout every time.
Fortunately, there is an easy fix for this; you just have to edit the file located at: /etc/gai.conf which is the configuration for getaddrinfo(). There you have to uncomment line ~54 which reads: “precedence ::ffff:0:0/96 100″, and you are all set! (assuming that every other option is commented out by default as in my case).