Al decir formatee que hiciste?
Has comprobado que sigues teniendo los números de Imei correctos. En ajustes los puedes ver.
Otra cosa arriesgada, pero vamos, o pierdes nada, es trastear desde el menú de información de dispositivo, que sale pulsando varias veces en 'almacenamiento interno' del menú info del movil.
Ahí puedes variar las redes y encontrar tu solución. Es ir probando. Suerte.