Back in 2001, as PC shipments slowed, the anti-viral industry tried to hype up PDA and cellphone viruses - selling software to those billions of phones had them salivating. Of course, no real threats appeared and (luckily for them) by 2003 Internet worms started to impact consumer and enterprise PCs and sales went up. Of course, desktop antiviral hasn't been saving anybody from anything, but since it has been on our PCs since before the Internet, everyone assumes it has to be there.
Fast forward to 2004 - worms and viruses aren't making the new lately. Magically, the cell phone virus hype kicks up again.
It looks to me like 2006 is the earliers possible time that cellphone viruses or worms could be a meaningful threat - and the answer is not repeating the mistakes of the PC and trying to rely on client side software.
The cellular companies should learn from the AOL's of the world and announce they will remove viruses before they get to your phone. Let's only go to expensive, ineffective anti-viral client software if that approach doesn't work. On the Internet, we are doing the reverse - ISPs are starting to block attacks as we've realized client side software is expensive and doesn't really work.