OK This worked for me:
First step was to find the version of ios that i was on
Settings> General>About (or whatever its called)
Download the stock software from this mirror that matches what you have
http://www.felixbruns.de/iPod/firmware/
During the restore I got error 1600. I think it has something to do with my hosts file being edited at some point. Click on finder Go> type in the box"/etc/" no quotes. Copy the "hosts" file to desktop, open with textedit. if at the bottom you have a line with ending with gs.apple.com I believe thats the problem, put a "#" at the beginning before the ip address. That sets that line to be ignored and no 1600 error (if youre on a windows box, use google to help u find the hosts file
Use itunes to restore iphone to restore software. Plug in iphone hold alt and click on restore, select the ipsw file that you just downloaded.
Should go through the process restoring you to stock ios. if you get stuck in recovery use tinyumbrella to kick you.
then restore your back up when the phone reboots so you have all your messages and phone numbers ets. Sync again, but dont allow the media or apps, just slow down the process later.
Then use itunes to update to ios5.01 as normal.
Good luck
Dont forget to Jailbreak using latest redsnow and install a siri port
----------
I had the same issue today both 1600 and 21 error. I got so mad I gave up. I came back a few hours later. I ran Bootcamp on my Mac (windows 7) I use that side for pc games... so for ***** and giggles i downloaded iTunes and restored both my phone. iPhone 4 CDMA 4.2.7 to 5.0.1 no problems at all then I restored my 3gs 4.1 to 5.0.1. ...your best bet try a different computer or delete iTunes and reinstall it. best of luck!
Cool that prob means the hosts file was somehow messing it up, as it would have been Mac side.
guess you can skip the part with downloading 4.1 or in that guys case 5.0.
