Go to Settings > General > About, and tell us what the modem firmware section says.
So an update. I managed to downgrade it to 4.1, somehow. iTunes threw up an error message saying it didn't like it (I don't remember the specific message, I think something about not being eligible for an update?), and I wanted to repeat the feat anyway, so I updated to 5.1.1. Currently, with 5.1.1 (9B206), the modem firmware section says "05.16.05".
And trying to downgrade on a clean MacBook Pro gets me error 20 every time. There is no third party software installed, iTunes and OSX are up-to-date (10.6.3 and 10.7.4 respectively), all updates applied.
My steps are as follows:
1) Connect the 3GS
2) Option+Restore in iTunes, select the restore file that utahman130 linked to earlier in this topic
3) Open, Restore, then iTunes produces the error "The iPhone "iPhone 3GS" couldn't be restored. An unknown error occurred (20)." and the phone is stuck in recovery mode with the Connect to iTunes image on the screen, the only way I know to recover from that is to restore using 5.1.1.
EDIT: Re-reading the steps above, I noticed I didn't put the iPhone in DFU mode. After doing this I still get the error message "The iPhone "iPhone" could not be restored. An unknown error occurred (1015)."
Steps are as follows:
1) Connect the 3GS to iTunes
2) Turn the phone off
3) Press and hold power and home on the phone for 10 seconds, release power and hold home for another 10 seconds, to place phone in DFU mode
4) Option+restore in iTunes, select the 4.1 restore
5) iTunes produces the error 1015 and the phone is in (non-DFU) recovery mode.