I had the same problem and tried 5 times to upgrade. Eventually found this via twitter that helped:
http://snapwidget.com/posts/2011/10/12/fix-iphone-could-not-be-restored-issue.html
I'm now running iOS5
Im now running iOS5 also.
I have tried a few different approaches as I'm sure many of you have, then gave this a go and it has worked. Bizarre to think just quitting iTunes, plugging the phone into a different usb could work..
heres the steps listed on the link-
If you're like us, you couldn't wait to get your hands on the latest version of iOS. It brings a magnitude of enhancements to your phone, the most interesting (to us at least) is iMessage.
Unfortunately after waiting more than an hour for the download to complete, we were greeted with a "iPhone could not be restored" message in iTunes. We had already updated to the latest version of iTunes 10.5, so we knew this could not be the issue.
This is what we did to fix is:
1.Unplug iPhone and quit iTunes
2.Switch iPhone to Airplane mode
3.Plug iPhone into another USB port (not the same one it was in before)
4.Restart iTunes
5.Click on the Update button to accept the new software update
Took me about 15 mins after that to have it running.
PS- Still, may have just been finally getting through to the servers