Tente o seguinte:
- no terminal digite: sudo nautilus
- com o nautilus aberto acesse: /etc/ppp/
- de 2 cliques no arquivo: options
- com o arquivo aberto procure o parâmetro: MRU
- substitua: #mru (algum número); por: mru 1400
- salve o arquivo.
- tente conectar, se não funcionar tente reinicar o pc e depois reconecte.
Um colega, que utiliza o ubuntu 9.04, internet 3G da claro e o firefox, estava tendo este problema, com o hotmail e a católica virtual da Universidade católica de Brasília, pois ele não conseguia postar no fórum da Universidade e nem logar no Hotmail. Este problema também foi verificado com usuários do Roteador Wirelees DI-524 da DLink (meu caso, hehehe), mas neste caso a mudança do parâmetro MRU foi feita na configuração interna do roteador. Tente esta dica. Não custa nada. Espero ter ajudado.