@oneeye Thanks for the info!
It sounds a lot like your problems came from installing a fake Kaspersky mobile app. These look exactly the same as the original, but don't do anything other than show ads, and try to SMS premium rate numbers and other nasty activities, certainly no useful virus removing activities. The Google play store is riddled with them and they often have very high ratings and lots of reviews (these are all fake, or from users who have been duped by the fake app too).
If you have your smartphone handy and you're reading this post from it, follow these instructions:
Firstly, follow these instructions (direct from the HTC support site) which will allow you to install the application:
You can then find the official Kaspersky Antivirus application here:
http://kms.kaspersky.com
The link will automatically download a .apk file to your handset, you should see it if you pull down the notifications from the top. It should be something like kisa_11.3.0.623.apk or kms_10.1.32_en-us.apk ~ depending on which version is automatically downloaded for you.
Tap the file listed to open it up and follow the on screen instructions to install. Update the definitions and run a scan, and of course be sure to post the results up here
Unfortunately resetting to the factory settings won't get rid of a malware infection as this only resets the settings and doesn't delete any malicious files which might be hiding etc. The malware then changes the settings back to what it likes and you're back to square one.