Tenia el mismo problema con Movistar. Probe mil configs y la solucion fue la siguiente.
Haz un Hard Reset y mete los apn de movistar de este post y listo. A funcionar a la primera.
Hay una aplicacion en el market APN Backup & Restore q te crea una copia de seguriadad de los APN en la SD. En el proximo HR solo tendras q restaurar los apn.
Salu2.