I first tried to put
GRUB_CMDLINE_LINUX_DEFAULT="ipv6.disable=1 quiet splash"
in /etc/default/grub. This disables ipv6 (no devices present), but doesn't solve the slow name resolution.
Wireshark confirms that AAAA requests are sent to the dns, but they don't get resolved.
Solution seems to be in
https://bugs.launchpad.net/ubuntu/lucid/+source/eglibc/+bug/417757/comments/75
So,
apt-get install pdns-recursor
and setting 127.0.0.1 as the dns for my specific connection in network manager solved the issue