+1. I always get emails about this and it is getting frustrating. Ever time it seems to fix the users problem if they go to Settings -> Applications -> Manage Applications -> All -> Market -> click "Clear Data" and then reboot.
Unfortunately for me, the proposed solution did not yield the desired results. I also tried booting into recovery and wiping my cache as well as several other combination of clearing market data and cache, then recovery and wipe cache. Wiping market data and cache after wiping cache in recovery. Not wiping cache in recovery and wiping market data, cache, reboot several times as it was inferred that it may take several times to work. Any other solutions? I am thankful for the responses and hopeful to find a solution that works.
Yes, this has worked for me and my wife's phone. I think I can narrow it down to the SD Card, and quite possibly something in the "android_secure" folder. You can either remove the SD Card and reboot without it and download (recommended) or enable USB, copy all the files in the "android_secure" folder somewhere on your hard drive and unplug USB and then try to download again (may need to reboot prior).
Not sure why this works, but maybe one of the Android geniuses here might dig into it and see? The clear cache thing never worked for me either.