I had one of those 3G upgrade experiences that started off with the terribly slow backup. Tremendously slower than the backup done normally in iTunes. Since I got that far, I had already downloaded IOS 4 into the Mac. Reading a “hint”, there seemed to be a suggestion to normally backup the iPhone using iTunes Sync and then either 1) restore 3.3.1 or 2) 4.0.0 . I anticipated that I might get asked what version to restore to.
In reality, the restore restored things to 4.0.0, then asked if I wanted to restore the data associated with my backup (which I said yes to). While things still took a while (including regenerating iPhotos for the iPhone), it moved and made progress.
I gather in reading other notes, that this approach also leads to a faster running IOS 4 on the 3G (time will tell).