Aloha mrat93,
You do NOT have to restore. I ran into this problem several times, and I finally figured out how to resolve it. Simply:
1. Connect your iPhone to your Mac and fire up iTunes (if it isn't running already).
2. In the Applications tab, deselect all applications, such that they will be deleted off of your iPhone.
3. Now that your iPhone is in "stock" condition, eject it from within iTunes (disconnect the sync cable), then reconnect the cable to resync your iPhone with iTunes.
4. This sync will create an initial backup, which will last around 1 minute. After the sync is complete, add all desired apps via iTunes (check them in the Applications tab), then repeat step 3.
5. This time, the backup should take a bit longer, as it is creating an initial backup for all of the installed apps. Once the backup has been created, repeat step 3.
6. For this sync, and all subsequent syncs, the backup process should take anywhere from 1 to 2 minutes total, depending on the number of apps added to, or deleted from, your iPhone since the last backup. Each of these subsequent backups are incremental in nature, or at least it appears so thus far.
The main issue is the firmware and the apps themselves. I couldn't figure out a causal relationship previously, but it seems that the DRM on the apps is firmware-specific. In other words, once you update the firmware, you'll have to re-install the apps for them to work properly. I did not find a causal relationship between this behavior and the deletion of all iPod and photo content, however. I think that something has caused corruption within iTunes, or at least the .xml file that resides on the iPhone, with each firmware upgrade starting with 2.0.1.
I did this with my iPhone, as I was frustrated with having to restore my iPhone 5 times just last week - I had to find a better way of keeping my media on my iPhone. I hope this works for you as well as it is currently working for me.

HawaiiMacAddict