Lo primero, comprueba que realmente está bloqueado. Hay teléfonos de Movistar, sobre todo de la primera partida, que vivieron libres de fábrica. Si está bloqueado, puedes optar por liberar el móvil por IMEI o por desbloquear el bootloader. Lo segundo es un poco más caro pero además de liberar el móvil te permitirá instalar rom cocinadas como CM7.