El problema es que Titanium Backup, o en mi caso yo lo hacía con Link2sd, intentan borrar de /system/app.
Las aplicaciones preinstaladas de las operadoras, en mi caso Yoigo, están en /vendor/app, por lo que los programas antes mencionados dicen que no lo encuentran.
La solución es que vayas con un explorador root a esa ruta y las borres directamente
