El problema es el Xposed, quítalo y verás que todo empieza a ir bien, a mi me pasó algo similar.
En cuanto a lo del cambio de Imei se puede hacer, vete al SAT a que te cambien la placa del tlf, es la única manera legal de hacerlo, de otro modo sería ilegal y aquí no apoyamos ese método.