Me ocurrió cuando estuve en una zona con cobertura GSM (EDGE) exclusivamente. El internet funcionaba en modo EDGE por ratos pero eventualmente perdí el internet por completo (dejaron de aparecer las letras al lado de las barras). Ni pasar a modo avión ni reiniciar las APN y apagar y encender el teléfono me sirvió (eso molestó un poco mis vacaciones en Taganga). La única forma de que me volvía a servir era entrando en una zona con cobertura 3G (UMTS) como mínimo, pero volver a entrar al pueblo hacía que se perdiera el internet nuevamente (otros teléfonos funcionaban en EDGE sin problema alguno).
Tal vez un par de veces me ocurrió estando en zona con cobertura >3G, en uno de los casos poner en modo avión y salir hizo que sirviera, en la otra ocasión me tocó apagar y encender.
Ya se soluciono y no supe como, Pq no me he movido del lugar y se por el teléfono de mi novia que no era problema de la red de movistar.