Caso extraño,por el tema de varios terminales y que suceda lo mismo.
A ver,a mí sólo me ha sucedido algo parecido cuando restauré una rom de un backup pero era por tener el Playstore con una versión anterior y lo solucioné actualizando la aplicación.
Otra cosa:¿Has mirado la configuración de los APN?.Igual también puede ir el error por ahí.
Un saludo