Hola chicos.
Yo tuve el problema de "Red móvil no disponible" en Movistar España. Después de mucho buscar, respondo los hilos que consulté con la solución. En mi caso, el IMEI estaba intacto y no liberé mi teléfono, sencillamente lo rooteé y le actualicé la ROM.
La solución pasó por:
1) entrar en modo Recovery -> Advanced -> Fix Permissions.
2) Si no tienes bien los APN, pones los que correspondan.
3) En Operadores Móviles seleccionas "Seleccionar automáticamente".
4) Reinicias, pones el PIN y funciona.
Espero que os sea de ayuda, saludos.
PD: Leído de Ñañe en HTCmania.