Sounds like you're downloading via iTunes and trying to sync to the phone. Have you also tried downloading directly to the phone?
FWIW, other people are reporting the same problem with other apps. For instance, check this thread on Apple's discussion boards:
http://discussions.apple.com/thread....20667&tstart=0
There's a bunch of useless stuff in that thread, but the user ended up calling AppleCare, they had him reinstall everything iTunes related, and the problem cleared up. I don't know if that experience is representative or not.