Debian / Ubuntu prefer to use IPv6 DNS Records. This leads to problems if the server supports only IPv4.
The problem can easily solved. We only need to change the config for getaddrinfo(). Open /etc/gai.conf and change
#precedence ::ffff:0:0/96 100
to
precedence ::ffff:0:0/96 100
For me it was line 54.