Al final no he hecho eso, pero tu indicación me valió de pista. En /data/dalvik-cache no había nada del Titanium (lo había desinstalado), pero en la carpeta /data/app estaba el apk, que tras borrarlo me permitió instalar la última versión de Titanium.
Muchas gracias a todos
