I deleted a ton of apps down to 731mb (29 apps) and it helps but I shouldn't have to do that. That's why I bought a 16gb. To hold apps. The AppleCare guy I spoke with said he's never heard of the problem. I went from 2.5 hours to 45 minutes. Still not acceptable. Painful.
I have no clue what to do on my end to fix this.
Nothing's going to be done with just folks complaining on boards.
Everyone needs to call AppleCare so they log this. Minimally, feedback email: http://www.apple.com/feedback/iphone.html
EDIT: Wow. I just did the 45 min. backup, sync'd my old iphone (instant), plugged back in the 3g and it's backing up again. Just minutes after the first big backup. This took a few minutes. With the 45 min backup, all I did was play a game for a few minutes between backups. I don't get it.