I am experiencing the same issues. I was having major problems with my phone, so I decided to do a factory reset. I tried downloading my original apps. Most downloaded and installed properly, but a lot of them did not. I was reading on this forum, and a solution was to purge the cache in the Market from the 'manage applications' section. All of the apps say 'computing' unerneith them. I cannot clear the cache, as I tap the button, but nothing happens as long as it's saying 'computing'. I still cannot install apps either. I can download them, but not install them. I am not rooted.
This works best when you can get wifi. Do the factory data reset again. This time after you re-sign into your google account do NOT do anything else with your phone until you get a notice in your notification bar that "xxx apps have been restored". Patience is a virtue.
Okay, after a lot of reading, and great advice. I finally figured out the solution to my problem. It was simple, and I can't believe I didn't try it sooner.
I simply removed the media card (SD).
After that, I was able to install all the downloaded material. Root the Droid X without problems, and 'freeze' a lot of the bloat ware (thanks to Titanium Backup), then reinstalled my SD media card, and viola! I was even able to install my old programs that were in my download folder on the media card.
I hope that this helps at least one person with the issues I had.