Minha conexão é Velox. Chega por telefone até um modem e deste o sinal é enviado a um access-point (que alguns chamam de roteador), de onde é disponibilizado para uma pequena rede composta por este meu notebook (um Acer TravelMate 4500), o notebook da companheira e um desktop de reserva. O primeiro DNS era local (10.1.1.1) e o segundo era do Uol (não lembro o IP dele), que a Velox insiste em usar. Mudei para os atuais justamente para ver se resolvia esse problema, mas não adiantou (apesar de que notei uma melhora em velocidade).
Quando não faço downloads grandes a velocidade é bastante aceitável, e os downloads ficam em média nos 63 Kbps. Mas se durante esse download eu tentar abrir qualquer página vai ficar o aviso na barra de status dizendo "Localizando a página X" até aparecer a tela dizendo que a página não foi encontrada.
O problema começou há poucos dias, depois que mandei o Windows XP (mesmo legalizado) para o espaço e instalei o Ubuntu 10. Mas estou fortemente decidido a não usar mais o Windows porque adorei mesmo o Ubuntu. E, apesar de não ser fera em redes, acredito piamente que é alguma configuração no navegador, no access-point ou no próprio Ubuntu.
Já tentei várias coisas. Mudei os servidores DNS, editei várias opções no about:config do Firefox, desinstalei extensões deste...