Estou prestes a resolver este problema também. Parece que esse problema está em mais distribuições, já que tenho o mesmo problema no Ubuntu 9.10.
Pode haver mais motivos para isso: problema no kernel, no driver do dispositivo de conexão à Internet, mas é mais provável que seja um problema no ipv6 ou no DNS.
Aqui está a maneira de desativar o ipv6: link (Isso não foi trabalhado para mim)
Então eu tentei mudar os servidores DNS, para abrir o DNS como está escrito aqui: link (Isso funcionou para mim, mas eu não gosto dessa solução, já que a atribuição do servidor DNS pelo meu DHCP está funcionando em outro sistema operacional)
Eu também descobri que o problema é que o Ubuntu está enviando primeiro as consultas DNS no IPv6, então há muito tempo para mudar as consultas para o IPv4 e obter resposta do DNS não suportando ipv6. Portanto, usar o DNS que suporta o IPv6 ou definir o não uso do IPv6 no seu computador pode ajudar nesse problema.
De qualquer forma, vou tentar resolver essa questão ainda, então terei uma nova experiência.
Eu sei que você usa outra distribuição do Ubuntu, mas pode ser exatamente o mesmo problema.