Some users have reported a loss of apps after the update to iOS 4.0, usually due to an upgrade error.
AppleToolbox reader Radu Popescu writes:
“I lost several paid apps from my iPhone 3Gs during the upgrade to 4.0. My purchases are on my iTunes account, but the apps that I purchased are not downloading. By the way, there was an error during the upgrade to 4.0, iTunes said it is regressing to previous image, but it did not and in the process threw away all my music, pictures, videos, and purchased apps.”
In most cases, this issue can be resolved by simply restoring from backup as described in this Apple Knowledge Base article. However, if your backup is corrupt, or if you are setting the device up as a new phone to solve a different troubleshooting issue, you can re-download any purchased apps by logging into your iTunes account and navigating to each app’s page. iTunes will not charge you a second time for already-purchased apps.
What if you can’t remember which apps you’ve purchased or download? This Apple Knowledge Base article describes how to view your iTunes purchase history and order numbers.