Algunas ROMs cambian el número IMEI del teléfono, no sé bien porqué. Si el IMEI que has facilitado para liberar el teléfono es el que venía en la caja del teléfono, y es distinto al que obtienes directamente del teléfono (hay que marcar un código que ahora mismo no recuerdo para obtenerlo, pero busca el Google), es normal que no sirva el código de desbloqueo.
Por otra parte, no se si volviendo a la stock ROM de Yoigo volverás a tener el IMEI original.