Apple has added a new layer of security to the iPhone 3GS. I mentioned it several posts earlier; it's the ECID field. When iTunes starts the restore process, they contact Apple servers to generate signatures just for your device. It's important you get these signatures for your phone before a new version of the software comes out. I had previously suggested doing this by dumping usb while the iPhone restores. But this is complicated.
Thanks to GeoHot purplera1n.com will help you generate a unique certificate for your phones iBSS. You will need to keep this certificate for possible use in the future.
Instructions can be found here: Windows, Mac