Las roteado y cambiado el Rcovery no? Pues lo primero que tienes que hacer antes de nada, es hacer una copia de la Carpeta EFS, que es donde está el IME, sin esa carpeta, jodido lo tienes para recuperar el IMEI.
Mira por XDA si hay algún tuto para recuperar el IMEI