For all you windows users the following link posted by ambarsaria works like a charm:
http://appldnld.apple.com.edgesuite.net/content.info.apple.com/iPhone4/061-7437. 20100621.5urG8/iPhone2,14.0_8A293Restore.ipsw
Just like he said, while holding down the shift key, in iTunes, click the restore button for your iPhone 3GS, and then select the downloaded .ipsw file. Of course you need to unzip it if your browser didn't do that for you already. Please make sure you back up ALL ALL ALL of your data before, because if I remember right, this will wipe your data.
Don't quote me on this, but mac users, I believe you can do the EXACT same thing, as long as you hold the Option (alt) key down, while clicking the Restore button for your iPhone 3GS in iTunes. But once again, make sure all of your data is BACKED UP!!!