I have the same type of problem. I clicked to upgrade to 6.1.2, it downloaded the program, it extracted the software, then gave the message that it was verifying the iPhone restore with Apple, then failed. The message is that "The iPhone cannot be restored at this time because the iPhone software update server could not be contacted or is temporarily unavailable."
Looking at the logs, there is a lot of activity with the update server, but at the very end it makes a 'personalized bundle' for the upgrade, then a particular server can't be reached to authenticate it and quits the process. Quel drag.
2013-02-21 00:21:27.000 iTunes[391:1c5c3]: amai: _AMAuthInstallBundleCreateServerRequestDictionary: using UniqueBuildID <CFData 0x7fd2cc5a4b00 [0x7fff7e4adfa0]>{length = 20, capacity = 20, bytes = 0x16c8202f9f54546c0f0bc02482d1872fb9667811}
2013-02-21 00:21:27.000 iTunes[391:1c5c3]: amai: AMAuthInstallRequestSendSync: SSO function returned NULL, SSO disabled.
2013-02-21 00:21:27.000 iTunes[391:1c5c3]: amai: tss_submit_job: SendHttpRequest failed 404
2013-02-21 00:21:27.000 iTunes[391:1c5c3]: amai: AMAuthInstallRequestSendSync: failed tss submission: Server not reachable
2013-02-21 00:21:27.000 iTunes[391:1c5c3]: amai: AMAuthInstallApCreatePersonalizedResponse: server request error: Server not reachable
2013-02-21 00:21:27.000 iTunes[391:1c5c3]: amai: AMAuthInstallBundlePersonalizePartial: failed to create ap ticket
2013-02-21 00:21:27.000 iTunes[391:1c5c3]: failed to personalize the restore bundle: Server not reachable
2013-02-21 00:21:27.000 iTunes[391:1c5c3]: AMRAuthInstallDeletePersonalizedBundle
2013-02-21 00:21:27.000 iTunes[391:1c5c3]: AMRecoveryModeDeviceCopyAuthInstallPreflightOptions: failed to personalize bundle
2013-02-21 00:21:27.000 iTunes[391:1e553]: iTunes: Restore error 1638