Thought I'd post a recent experience in case anybody has a similar problem and it helps them.
I finally got round to upgrading my iPhone to 4.1 last night.
I backed the phone up, downloaded the software and hit the update button. I had several instances of a message which basically said that iTunes couldn't contact the software update server to verify the download. The upgrade therefor came to a grinding halt before it had even started!
I left it a while and tried again. Eventually success seemed to arrive and the update started to install. All seemed well until the very end when iTunes had to contact a server again to verify the upgrade. At this point the wheels fell off and the update failed. I was presented with a message informing me of a "3004 Error" and an iPhone in recovery mode that was essentially a brick and that wouldn't restore from my backup. Every time I tried to restore the phone I got the original server issue message.
After two hours of searching Google for a resolution, unsuccessfully, I was stumped as to what to do about it. As a last resort I decided to run Onyx, with all automated tasks ticked, and restart the Mac.
I couldn't say what the problem was, or how Onyx fixed it, but I was able to Restore/update my iPhone on the first attempt.
Last night was a very late/long night.