I did some digging and ...

The article doesn't mention which app was malicious however they did mention that the app publisher went by the name of "jackeey,wallpaper".

I ran some queries and it seems like the developer that publishes apps under "jackeey,wallpaper" also publishes under "jackeey.wu".

A list of the apps published by this developer are here (most of which are wallpaper apps):

http://andbot.com/developer/jackeeywallpaper

http://andbot.com/developer/jackeey-wu

http://andbot.com/developer/jackeeywu

If you search the market for "Jackeey" you'll get several dozen wallpaper apps. I think the article is treating all of them as a single app, which explains the "1.1 to 4.6 million" downloads: they just added up the lower and upper bounds of the ranges for each individual app. And as I said above, they don't appear to be requesting permissions that would let them do most of the nasty things described.