Problem jest w owym zrootowaniu telefonu.
Próbujesz zainstalować aplikację która jest w markecie zaznaczona jako PROTECTED, tak zaznaczone aplikacje w ogóle nie powinny się pojawiać na telefonach developerskich/zrootowanych (market nie rozróżnia telefonu zrootowanego od developerskiego). Jest to jedno z ostatnio wprowadzonych zabezpieczeń anty-pirackich w Markecie, po aferze z developerami którzy ściągali sobie aplikacje na zrootowane telefony, podmieniali podpis cyfrowy apki i wystawiali na markecie jako swoje aplikacje, często/gęsto dokładali tam wtedy do aplikacji wirusa/trojana.
Jak chcesz instalować normalnie tą aplikację jako root to w domyśle instaluje ona się dla wszystkich "użytkowników" czytaj: root-a i zwykłego usera. Z racji że aplikacja roota nie toleruje to instalacja się wywala. Jak instalujesz "as private" to apka instaluje się tylko dla zwykłego usera.
Pozdrawiam