Los datos de tu compañia los tienes bien en el teléfono?
Algo he leido sobre un problema parecido y pone que el problema era de la linea de telefono y se lo soluciono la compañia.
Yo les llamaría por si es algún problema de la linea, y de pasó comprobar si la configuración del teléfono es el correcto para esa compañia.