I could use this article as the basis for a gratuitous swipe at Android and laugh at people who protest Apple's rules that force all installations to go through their App Store, but that would just be rude.
More importantly, please note the following text from the article:
The contaminated apps Lookout found were harvested from Google Play, infected with a payload and then republished on third party app sites enabled by Google's open app model allowing Android users to find and download apps from multiple stores.
In other words, if you get your apps from Google's official Play store, you should (it would seem) be safe from these really really nasty pieces of malware. But if you're downloading apps from third-party stores, watch out - you may have no way of knowing that what you get has been tampered with. Ironically, this supports Apple's claim that allowing third-party app stores is inherently dangerous.
Also noteworthy is that this is not (as the headline seems to imply) spread via ads. A legitimate app is not going to be compromised by this malware simply as a result of loading ad images. At least not in the current version of this malware.
Finally a bit of speculation. The article says that the malware installs itself as a system app, so the normal device-wipe procedure doesn't work. I would assume, however that if you completely wipe and reinstall Android (via a USB cable, much like how some people install unofficial/unsupported operating systems), that should purge the malware. So you shouldn't need to discard the entire phone. Someone who has the tools to completely re-image a phone with the carrier's original bundle (like the carrier's own tech support staff) should be able to recover from this.
iPhones can (as far as I know) be completely re-imaged using the iTunes application on Windows or Mac OS X. This is actually part of Apple's recommended procedures when an iPhone gets messed up to the point where nothing else works. I think Android should provide something with similar capabilities, for just this reason. It may be politically tricky, since each phone's manufacturer/carrier combination is going to have a different image, but there's no technical reason why this can't be done.