...
Android can, and will, from time to time get spyware and adware. The best part about Android, is that on a non-rooted device you can simply do a factory reset and the problem is gone. As a preventative, look for a legitimate anti-malware app to install to scan your phone. Sadly, the ones that cost money are more likely to be legitimate... I wish Comodo would come out with a free mobile app lol.
No disrespect but your views would be all good if you wasn't posting this on a site dedicated around rooting their device, how much you bet there is only a small handful of users hear not rooted...
Rooted devices are open to be infected and once again I will say, even if the device codes cant be compromised (Which is possible but this site is built around working around, finding and getting around security restrictions) it is also possible to configure a script that will run from a pc when device is plugged in to modify devices system files if they want.... Can someone say Easy Root??? 
Its really time to get over this false security that anything made by man can not be defeated by man...
There is an entire subforum dedicated to rooting, but I would say that of all the Android forums I visit, AC has the most
non-root users of any of them. This isn't a bad thing, I'm just saying that while many sites are solely dedicated android development, this site seems to be more geared to general help/support, as well as a news and information sounding board. Especially when you're posting to the main forum (and not the root subforum), I see nothing wrong with giving advice aimed at non-rooted users.
On that note, however, root users can do a factory reset as well...i.e. just re-install the ROM they're currently using without restoring data. Some may say that a rooted device is more susceptible to malware because root access is available, but you do have to manually grant any apps that want su access, so it really is still the responsibility of the user to make smart choices when installing/updating apps.
I could get into a multi-page rant about how worthless anti-virus software is for ANY platform (inc. Windows), but that would be a bit off topic...
My advice to the OP, if it hasn't already been fixed, would be to try to find and uninstall the offending app, and if that doesn't fix it, bite the bullet and do the factory reset. As far as the risk of data being stolen, every app will clearly define what data they require access to, so you may want to check what permissions the app has if you're able to. Many people don't even consider this when installing apps. Checking the comments are good way to see not only if the app works as it claims to, but also what concerns folks may have about the permissions an app is requesting. ANY APP WITH PERMISSION TO ACCESS PERSONAL DATA COULD POTENTIALLY "STEAL" THAT DATA, REGARDLESS OF WHETHER OR NOT IT FLOODS YOUR DEVICE WITH ADS (although that certainly may be a tip-off that the app developer has misguided motives).