I have this problem. I have about 4 screens of apps, and about 5 or 6 of 16gb used. A backup will literally take a few hours to do, but I almost always cancel.
I've been wondering if I should let it do one of those backups and then do a restore and see if that fixes anything, but I'm kind of hoping a new firmware or iTunes update fixes it.