Sugiro verificar se o IPv6 está ativado como primeiro passo. No menu Sistema, abra Conexões de Rede, selecione sua interface, clique em Editar, clique na guia IPv6 e verifique se Ignored está selecionado.
Eu instalei recentemente o kubuntu 9.10 AMD x64 em uma HP 6830s. A instalação correu bem, com apenas um problema: quando tento usar a internet, é incrivelmente lento. Não consegui instalar o Firefox nem nada que exija a internet. Eu tentei a maioria das soluções que encontrei pelo Google, mas nenhuma delas resolve o problema.
O que posso fazer?
Sugiro verificar se o IPv6 está ativado como primeiro passo. No menu Sistema, abra Conexões de Rede, selecione sua interface, clique em Editar, clique na guia IPv6 e verifique se Ignored está selecionado.
O seu problema não parece ser um problema do (K) Ubuntu, mas do seu roteador ou ISP (veja Launchpad para um relatório de erro muuuuito). Portanto, eu aconselho você a não desativar o IPv6. Embora isso possa ajudar em curto prazo, o problema provavelmente o cairá novamente em um ou dois anos, quando o IPv6 assumir o IPv4.
A primeira coisa que você deve tentar é atualizar o firmware do seu roteador. Isso resolveu completamente o problema para mim (e para os outros). Se isso não ajudar, você deve bugar seu provedor de serviços de Internet ou o fabricante do roteador até que eles consertem as coisas.