Encontrado el error, por si alguien mas le pasa, la solucion esta aqui:
- Con un gestor de ficheros, activamos root y borramos los siguientes directorios: /mnt/expand/very-large-number/data/app/com.keramidas.TitaniumBackup /mnt/expand/very-large-number/user/0/com.keramidas.TitaniumBackup /mnt/expand/very-large-number/user_de/0/com.keramidas.TitaniumBackup
- Instalamos de nuevo Google Play
A partir de aqui ya se podra ejecutar Titanium Backup normalmente