Yo tengo O2 (que es de Movistar) y sin problemas. Probad (si tenéis la posibilidad) una SIM de otra compañía para descartar que sea la compañía y no el móvil. Por otro lado, si hace años que tenéis esa SIM, pudiera ser la misma SIM que falle.
Además, podéis probar vuestra SIM en otro móvil, y ver qué cobertura tiene, o si tiene fallos de cortes, etc....
Un saludo