The problem is caused by Ubuntu requesting everything by IPv6 first even if there are no IPv6 Interfaces configured and timing out each time when it doesn't get a response.
The workaround in firefox is to go to "about:config", just type it into the address bar and hit enter. Then change the value network.dns.disableIPv6 to TRUE.
The bug can be tracked here:
Firefox Ubuntu 9.10 Karmic Koala DNS