iReb 'solution' worked on 3GS with similar 1604 issues
Just wanted to share that I had a problem with my 3GS where it would never boot (always stuck at apple logo indefinitely), would get to DFU mode, but would always fail with 1600 or 1604 error when trying to restore from DFU using either official or custom 3.1.2 firmwares.
I was at my wit's end and about to take it into the Apple store, when I saw mention here of the iReb tool, and even though it is for 3G, not 3GS, I thought I'd load it up and see what it could do.
To my surprise, as soon as iReb started, my attached iPhone popped into normal (non-DFU) recovery mode, which I had been totally unable to get it into. From there, I again tried a Shift-Restore into a custom 3.1.2 firmware, and it worked!!! Note that I did not try any features or functions of iReb, but when it starts, it must 'prep' the attached iphone somehow to get it ready to work on.
TL;DR version: if you're stuck on a 16xx error - even with a 3GS - try running iReb to 'cleanse out' your phone and get it into a proper recovery mode at least, then proceed to restore from there.
Hope this helps someone out there on the interwebs (or myself if it happens to me again and I have to Google the error)!