Penso tu possa installare anche con il root... ma è presto per dirlo... invece con una recovery modificata penso non sia possibile...
Probabilmente avevi cancellato qualche file di troppo con l'app Clean Master (a volte la scopetta ramazza un po' troppo!).
Penso che tu non abbia usato titanium Backup... devi usare quello!