Yo veo 3 posibles casos:
1)Que estes poniendo una tarjeta no movistar.O que el movil no sea de movistar y te hayan dicho o pienses que si, porque la carcasa tenga el logo de Movistar(la pueden haber cambiado).Yo probaria con otras tarjetas.
2) Que el movil este bloqueado por IMEI.Lo suele bloquear la compañia cuando la llamas diciendo que lo perdiste o que te lo robaron. LLama a la compañia para ver si te pueden ayudar.
3)Y por ultimo, cuando cambias de SIM en el movil, viene una opcion de que tengas que meter un codigo para que se encienda.de fabrica, suele venir el 1234 o 12345. si no entran, es posible que el dueño anterior lo hubiese cambiado por otro. Contactar con el que te lo vendió
suerte