Eso es justamente lo que hay que hacer para hacer una instalacion limpia, o con "clean for a new rom" o meterse en formats y hacer system, boot, data, cache, dalvik, si no se hace de una de estas dos maneras los fallos los tienes asegurados, tambien es conveniente hacer format SD interna, siempre que la nueva rom la tengas en la Sd externa, claro. Es muy dificil ayudar cuando alguien dice que ha hecho una instalacion limpia y no ha sido asi.

Gracias por comentar como se hace.