In Karmic, DNS lookups take a very long time with some routers, because glibc's DNS resolver tries to do IPv6 (AAAA) lookups even if there are no (non-loopback) IPv6 interfaces configured. Routers which do not repond to this cause the lookup to take 20 seconds (until the IPv6 query times out). [src: http://www.democraticunderground.com/discuss/duboard.php?az=view_all&address=240x1723]
So it was my (otherwise unevenful, as it should be) upgrade to Karmic that caused this!
The workaround for Firefox is to go into about:config and change the value for "network.dns.disableIPv6" from 'false' to 'true.'
And on this site, the system wide workaround:Using your favorite editor using sudo, edit /etc/default/grub and change: GRUB_CMDLINE_LINUX_DEFAULT=”quiet splash” to GRUB_CMDLINE_LINUX_DEFAULT=”ipv6.disable=1 quiet splash” then sudo update-grub
Just to find out that I still have grub 0.97 and not 2. So for now I'll have to make due with the firefox patch, which works fine. EDIT: Aha, that's why:GRUB 2 will be installed by default on NEW installations of Karmic. If you have upgraded from Jaunty 9.04 to Karmic 9.10 you can follow the install instructions for Jaunty 9.04 below. [src: https://wiki.ubuntu.com/Grub2]