Me pasó exactamente lo mismo hace poco tambien de movistar liberado por imei.
Por lo que sea la efs se corrompe y pierde la liberacion, la solucion meter el código de desbloqueo o restaurar una copia de la efs.
Para restaurar la copia yo simplemente copie todas sus carpetas y archivos desde la SD a /efs con root explorer y reinicie el terminal.
Saludos