Sofro o mesmo problema com a Claro; de temos em tempos, eu ligo, registro umas 5 reclamações de lentidão, eles falam que estão implementando melhorias e a velocidade melhora alguns meses. O ponto é que a rede 3G está saturada e eles não tem como fornecer a banda total, então, de 100.000 assinantes, se 200 reclamarem, eles dão a largurar total de banda contratada pra esses poucos "chatos" tudo fica bem pra operadora porque tem 99.800 pessoas usando um serviço ruim sem reclamar.
Também tive alguns probleminhas para conseguir conectar depois que decidi abandonar as Janelas e optei pelo Ubuntu, mas era uma simples questão de configuração. O modem ficou um pouco lento, mas também observei isso na máquina com WinXP; ou seja: problema na Claro e não no Ubuntu!