Yo no he hecho ninguna recuperación de aplicaciones a las que haya hecho backup.
Pero estuve leyendo en este mismo foro y comentaban lo siguiente. Cuando haces backup estas aplicaciones se van guardando en la SD.
Es recomendable guardar los archivos que has hecho backup en tu PC, están guardados en el siguiente path: /sdcard/TitaniumBackup
Una vez ejecutas el titanium backup en la nueva rom o movil te deberían aparecer las aplicaciones "backupeadas".
De todos modos, a ver si alguien con más experiencia lo confirma.