My 3GS was jailbroken with the 3.0.1 firmware and is a legit ATT phone. I have gotten the 1600 error on two different Macs and a 1602 error on a windows box. Retried it many many times, remaking the firmware, etc. All with no success. I spent a couple days just trying it because many reported that "it eventually just worked". Well I gave up until I saw the suggestion to Just plug your iPhone, start iTunes normally and press Alt+Restore and IT ACTUALLY WORKED! I even decided to try a restore from backup instead of setting up as a new phone and that worked as well (probably not recommended). I have no idea why this works or that it was even an option. I do know that MANY are having this issue and am posting this here for more visibility in hopes that some of you can get things working. No DFU mode, no recovery mode, just plug the phone in like normal and do Alt+Restore in iTunes.