I just posted this another thread -- basically if you synced from a backup that was created from a jailbroken 3g or 3gs, that might be your problem. I had very similar issues, until I tried restoring in DFU mode -- read my response below that was posted in reply to another youtube video:
Looks like you synced from a backup that originated from a jailbroken iphone -- I know this because that's the only way the battery % will show up in iOS4 until it's jailbroken for the iPhone 4... Anyway, my phone pretty much stopped being able to use cellular data last night after syncing from my macbook (which had previously backed up a jailbroken 3g). After the sync, I got some error messages -- but largely ignored them bc everything seemed to work fine. Shortly thereafter, I couldn't get more than ~10kbps over the AT&T network (normally I get ~2500kbps). Soft reseting the phone didn't help. It didn't matter if I was touching the lower left corner of the phone either. Basically, I could only send/receive data via wifi at that point.
Finally, I decided to restore iOS4 in DFU mode. Now everything is (sort of) OK. My signal strength still goes down if I short out the two antennas by holding the lower left of the phone in my left hand, but if I put a silicone case on the phone or if I simply do not touch the lower left corner, all is well...
