Debes buscar freedom mediante Google, no está enfocado la playstore.
Si colocaste otra sim y dices que no te toma te refieres a que:
No tienes señal?
O te pide código de desbloqueo al inicio?
En caso de no tener señal debes ingresar a ajustes/más redes/redes móviles/operadores de red y dentro de esta opción seleccionar la red del nuevo operador de la sim introducida.
Me parece raro que te cambie de imei puesto que el programa a mi entendido hace una liberación en base a tu imei y en ningún momento lo modifica, constataste que cambió el imei que aparece en la app y el de la caja de tu equipo?...