Aloha nickspohn,
I know what you can do, but you'll have to follow this step by step. To answer your question, setting you your iPhone as a new phone is the way for you to proceed at this point, but you may still experience the same issue again. You're either running iPhone firmware 2.0.1 or 2.0.2, right? I have found that iPhone firmware 2.0.1 caused more issues than it resolved, and that is probably why iPhone firmware 2.0.2 got released within two weeks of the releasee of iPhone firmware 2.0.1. Apps installed when iPhone firmware 2.0.1 was resident on an iPhone seem to not run well under iPHone firmware 2.0.2.
I had several issues with iPhone firmware 2.0.1, but have been able to resolve all of them. If you follow these directions to the letter, they should work for you. Additionally, you should see a slight bump in battery performance as well as 2 minute backups (or thereabouts, depending on the number of apps you normally carry - my normal load is around 47).
1. Plug up your iPhone, but don't restore to a backup. Instead, set it up as a new phone. It appears that your backup file(s) are corrupted, so setting up your iPhone as new phone may be the only way to proceed.
2. Once the firmware (hopefully 2.0.2) is loaded, your iPhone will restart at least once. It will then sync basic items, such as address book, calendar, and bookmarks. When it starts to sync apps, click the 'x' to the right of the progress bar in the top portion of iTunes.
3. Click on the Applications tab and deselect ALL of the applications listed. This will effectively delete them from your iPhone. Bear with me, this is an important step.
4. Once the apps are deleted, eject your iPhone from your Mac, unplug your sync cable, then reconnect your sync cable. Your iPhone will sync to your iTunes library once again, then create a backup. This backup should take less than 2 minutes, and it is effectively a "stock" or "clean" backup. Note the time the backup has been completed. If you ever need to backup to a known clean backup, this will be the one.
5. Next, click on the the various tabs (Music, Photos, Applications, etc...) and select all of the media you wish to load onto your iPhone and click the Apply button to sync your iPhone. This may take a while, depending on the amount of content being installed.
6. Once that is complete, repeat step 4. The major difference now is that this backup, which will take longer (mine took around 20 minutes), contains a TOC of all your media, as well as the initial state of all your apps.
Now you can use your phone. You have updated your media files and apps with the latest iPhone firmware and iTunes versions, so everything should be golden. Now, whenever you sync your iPhone, each backup will be incremental, which is a function of iPhone firmware 2.0.2.
Take this with a grain of salt, but from what I can determine, the DRM applied to apps on an iPhone with firmware 2.0.1 fail to run properly under iPhone firmware 2.0.2. It is as if the DRM is firmware-specific, with respect to iPhone firmware 2.0.1 only. I have experienced no issues since I followed the above procedure with iPhone firmware 2.0.1, and was able to upgrade to iPhone firmware 2.0.2 without incident. Whatever caused these issues was obviously fixed with iPhone firmware 2.0.2.
I hope this helps you resolve your issue. I've been beating this drum since last Saturday, when I implemented it on my iPhone, but I've been rock solid since then - 100% of my issues have been resolved and I have experienced no downtime, dropped calls, etc... All of my audio and video files are still resident, and none of my apps have crashed. As of now, my iPhone 3G is as stable as my 1st gen iPhone.

HawaiiMacAddict