Hola, a mi me paso exactamente lo mismo, compré hace casi 1 año un s2 de movistar por ebay, lo liberé y como yo tenía simyo (red orange) no noté nada, ahora me he cambiado a vodafone y no me funcionaba, total que tras mucho indagar, en movistar me dicen que está bloqueado por imei por robo o pérdida, lo curioso es que con simyo y orange va, yo al final he probado de todo y borrando el archivo nv_data.bin o algo asi y me ha cambiado el ime al 004999010640000 y ahora funciona todo, pero me da a mi que en breve tendré problemas, te lo comento por si quieres probar como solución temporal...