Eu estava com os mesmos problemas que você em minha máquina. De uma hora para outra ela parou de navegar nos sites e apenas os sites do google (gmail, notícias, imagens, orkut, etc) abriam. Cheguei a bootar a minha máquina com o CD 9.04 e o problema era o mesmo. A solução que encontrei foi diminuir o MTU de 1.500 para 1.400.
Para fazer tal mudança, você precisa clicar em Sistema, Preferências, Conexões de Rede.
Clique em sua conexão, e abra editar.
Na tela que abrir, mude o MTU de 1.500 para 1.400.