Ese problema que tienes,puede deberse a muchas cosas:
-Un mal flasheo.
-Olvidar hacer alguno de los wipes.
-Instalar aplicaciones con datos.
-Una aplicación que entre en conflicto (me decanto por ésta).Hay veces que es mejor hacer una limpieza completa de esa desinstalación (eliminar hasta la carpeta que había anteriormente de esa aplicación para que sea una instalación limpia completamente).
Yo he usado todas esas que dices y no me solían dar ese fallo.También hay que tener en cuenta que realizaba un nandroid cada semana y eliminaba los anteriores dejando siempre el que usaba en ese momento y que funcionaba correctamente.
También solía usar SD Maid Pro para hacer limpieza (una vez al mes).
Un saludo y espero haberte ayudado
