A mi me pasaba lo mismo(soy de tuenti) tuve que configurar el APN (Ajustes/mas opciones/redes moviles/APN) cada compañia tiene su configuracion, en el foro si no recuerdo mal habia un tema con todas las compañias, espero haber ayudado
EDITO:
Aqui esta la confi. de cada compañia, gracias a @gmpdelfin por la info.
http://www.htcmania.com/showthread.php?t=309324