I had the same problem yesterday, but I fixed it right away. I read on some forum that if you simply delete the last app you added to your phone (cuz that may be what caused the problem) and load a new free app or update a free app (I did the latter), the problem will go away. Some people said the problem came back after a few hours or less, but everything is working fine on my iPhone now. I am also hoping that the 2.1 update will stop this from ever happening again. Good luck!!
I have this occasionally, especially with apps installed directly on the iPhone (rather than side-loaded via iTunes). Often, a power cycling will correct it. Otherwise I delete the App and reinstall it via iTunes.
I was having this problem on a regular basis, usually after synching my phone. I run Vista, this problem does not seem to affect those running Macs.
I seem to have solved it by not synching the apps (in iTunes with your iPhone plugged in go to Applications and untick the "Sync Applications" tick box). Since I have started doing this, my apps are fine.
The only issue is that you need to plug in the iPhone in order to access the synching interfaces which might mean one more uninstall and reinstall of your apps.
I just got a new iPod touch yesterday for Christmas. And I was at a different house where I bought a few apps from my step moms credit card and when I got home the apps would not load. I resynced it and everything but I can't play any apps unless they came with my itouch. If you have any suggestions I can try to use without having to delete everything that's semi simple...that would be great. (: