Ese fallo suele ser de la tarjeta sim, como el coste de una sim nueva no es elevado, es la primera opción, una vez que hayas buscado la red manualmente.
Vete a la tienda movistar mas cercana y que te hagan un duplicado, si no es eso, obviamente como dice el compañero rovertovilla, toca restaurar a valores de fábrica y finalmente, y si nada de lo anterior funciona, al SAT.
Suerte!!