iPhone update server could not be contacted, but why ?

During the update and restore process, iTunes needs to contact Apple. Ensure that your computer has the following ports open and can access these servers:

* Port 80
* Port 443
* phobos.apple.com, albert.apple.com, gs.apple.com

You must also open access to the following VeriSign servers:

* evintl-ocsp.verisign.com
* evsecure-ocsp.verisign.com

You may need to update, properly configure, disable, or uninstall built-in firewalls and other security software to prevent interference with iTunes.

Any firewall on your router? If so, make sure its turned off. The biggest single cause of the problem you're experiencing is security software somewhere in your system.

That is your problem & it would have been extremely helpful it you had mentioned such in your first post. You will only be able to restore your phone as a new device in itunes.

No guarantees this will work, but try this: First, find & delete ALL .ipsw files on your computer. Your profile says you're using OS X, so they should be located here:

~/Library/iTunes/iPhone Software Updates

Next, see if you can force the phone into recovery mode:

Leave the USB cable connected to your computer, but NOT your phone, itunes running, press & hold the home button while connecting the USB cable to your dock connector, continue holding the home button until you see “Connect to iTunes” on the screen. You may now release the home button. iTunes should now display that it has detected your phone in recovery mode, if not quit and reopen iTunes. If you still don’t see the recovery message repeat these steps again. iTunes will give you the option to restore from a backup or set up as new. In your case, make sure you select "NEW".

When it gave you the option to restore, did you click yes? What exactly was the error message & what version of itunes are you running?

Did you hit the restore button?