I'm having the exact same thing. I just restored my iPhone after doing a reset of it. It seems to function just fine now.
By the way, there was nothing special that changed, but it sure does seem odd that both you and I had the same thing happen at almost the same time. I did upgrade the carrier settings on Friday and rebooted, but hadn't synchronized until just now.
Hey, i tried Gavin's answer, but, it didnt help Me, but, i found this(i know, this is not our error, but, it was fixed):
"During restore operation on my iphone, i have this error message in French :Une erreur inconnue sest produite (-9808)This problem of connexion was due of incorrect paremeter in IE.Please check tools/Internet option/advancedCheck revocation.De-flag this option and restart itunes Windows XP Pro"