For one thing, there is a major distinction between RESTORE mode and DFU mode. You might think you are in DFU (full-blown) when they are actually in Restore (semi). DFU is a blank screen. Restore is a screen with a USB cable or Steve Jobs speaking russian, depending whether is a stock iPhone or pwned iPhone.
IMO you should start all over and use Pwnage Tool, not RedSn0w. Use this tutorial at
http://www.iclarified.com/entry/index.php?enid=13001. You'll be repeating the step of building a custom IPSW, but so what. The cool thing with PWnage Tool is that it steps you through putting your iPhone into DFU mode and lets you know if attempt was successful. Once you get into DFU mode, you are stone-free to inject IPSW.
The thing with redoing your iPhone Restore-stye vs DFU-style is that DFU is more root-level and complete. I think Restore is more quick-and-dirty and that Apple's real purpose for it is for users to get their Contacts and Store-bought Apps back onto phone rather than major system-level changes.
One note: At step six, choose No. You already said you don't want or need your baseband changes. No = Leaves it be. Yes = Gives you opportunity to roll in that wacky iPad baseband.
Another note: Every Pwnage Tool jailbreak I've ever done has asked, after the building of the IPSW, if your iPhone has ever been pwned before (my iPhones were earlier models than yours, though). I always followed conservative protocol and answerd NO because that lets you continue on with the DFU-variety injection mode. Answering Yes, would steer you to the shortcut route of Restore-style injection method. You may not get asked this since 3GS is different, but if you do, answer No. The whole point here is to make sure you are going DFU.
