I personally had the opportunity to try to repair an infected smartphone with this trojan, and despite all the methods known to me, removal was unsuccessful in all cases.
I am quite scared of the (lack of) security mobile phones offer nowadays. I use a 3rd party antivirus for checking the things I install, but I am aware that some things can easily hidden from antiviruses too.
The phone you had in hand was rooted or not? I hope that only rooted phones are affected...
Also, maybe putting another ROM onto that phone would help get rid of that piece of.. trojan.
Malware infected apps rarely makes it to be added on playstore.
It was this year when Google announced me I have installed an app that doesn't behave right. It was only some ad abuse, I think, but I had the app installed for over a year until Google woke up.