I'm in the same exact boat. Also wondering about the text message thing.
If you have no data like myself and smileyboy ^ more than likely a clean restore (possibly from DFU mode) and NOT from a backup, should work for you.
1st restore. I upgraded yesterday from a jailbroken 3.1.3. After the upgrade went smooth, I restored from a backup and half way through it said it couldn't add my 16+gb of music b/c there was only 1.82gb free... but the bar at the bottom showed 25gb free. Don't know what happened there but it failed miserably if I tried to sync again... errors similar to "device full" or "internal error".
2nd restore. Worked fine again and I restored from a
different backup. When it tried to sync my Apps it gave an error something along the lines of "Internal device error" and shut off. Fail again.
3rd restore. Everything worked well and restored from a backup just fine... but like stated above from smileyboy - no data... Edge or 3G. Reset network settings multiple times, tried everything I could think of to no avail.
4th restore. Restored from DFU mode this time. Restore worked fine and set up as a new iPhone. Everything worked fantastic - including Edge & 3G. In order to troubleshoot (and b/c I was curious) - I wanted to see if it was truly DFU mode that fixed it or if it was my backup that was corrupt from the start. So I chose to restore from a previous backup and now the phone has no data again. It will work on wifi though.
So. After many hours of frustration I've come to the conclusion that
it was most definitely was some sort of corruption in the backup file itself. Possibly due to the jailbreak corrupting the backup somehow?
With that said, I'm trying to figure out the best way to go about "starting over" on a clean restore tonight. I currently do not sync contacts but I'm thinking the easiest would be to sync via Google Sync for contacts and then manually install my apps. The only app that has data that I DO NOT want to lose is 1Password - but I've backed that up (a few times, lol).
What about text messages? I've literally got years of texts from maybe 30 people that I'd prefer to not lose. I'll have to Google a solution for that but if anyone has ideas, please let me know!
I can say, after using 4.0 intermittently, it runs 100% smoother than 3.1.x did on my 3GS. I'm impressed again. If it's running this well on my 3GS I seriously cannot wait to see how the iPhone 4 will handle it.
Thanks for reading my rant and please feel free to chime in with any ideas!