Vuelve a intentarlo con Titanium, utiliza la versión pro, que la puedes descargar del siguiente enlace:
Descargar Titanium Backup Pro Key 6.1.0 [Apk] [Full] [Zippyshare.
Yo lo hice de la siguiente forma: instala el apk de titanium en una carpeta de la msd, ejecútalo/instálalo y haces las copias/respaldo de las apps de usuario más datos que consideres.
Flasheas la nueva rom, una vez arrancada ejecutas el apk de Titanium que tienes en la msd y restauras las apps que necesites.
A mi me funcionó muy bien ya que haces el respaldo y la restauración con la misma versión de Titanium y reconoce sin problemas las copias de seguridad. Encima con la versión pro te ahorras de autorizar una a una. Eso sí, restauro apps de usuario nunca de sistema. No cambio mucho de rom. Suerte.
P.D. consultar algún video en youtube, de como hacerlo, me ayudó para hacerlo con más seguridad.