I have had to do two restores on my 1st gen iPhone over the past week (apps stopped working and my music disappeared), and after doing some reading on the ‘net (and hearing Leo Laporte from Twit.tv talk about it) I have realized what was causing the problem: An app I had downloaded from the app store using the App Store portal ON THE IPHONE (and not through itunes) fails to install/download, which ends up (I think) completely hosing up the DRM the phone uses to track the content on the phone (apps/photos/music). After this happens, none of the third-party apps work and the music is still on the device but “invisible” to the user.
So, please, take my advice: USE ITUNES TO DOWNLOAD APPS. You may find this prevents a great amount of headaches (it was a REAL headache for me last week, cause it happened when I was out of town and away from my main itunes library).
I thought this situation was “fixed” with the 2.01 update last week; guess not. Hopefully 2.1 will resolve this issue.