Should be a fix here somewhere.....
I had the same problem (after doing the same thing, installing Winterboard on my purplera1n RC2 iPhone 3GS), follow these specific steps and you'll be golden:
Originally Posted by Bry279
1) Download redsn0w 0.8
2) Download 3.0 IPSW for 3GS
3) Open iTunes
4) Plug iPhone into Computer. I don't care what the current state of the iPhone is at present, just plug it in to the computer with iTunes open.
5) Hold Power and Home for 10 seconds until the phone cuts off.
6) YOU HAVE ABOUT ONE SECOND TO DO THIS, SO DO IT QUICKLY: Immediately after the phone cuts off, release both the Power and Home buttons and then press them again and hold them for 10 seconds. You should note that the Apple logo DOES NOT re-appear.
7) Let go of the Power button and keep holding Home.
8) Poof, 3.0 3GS in DFU mode.
9) Use redsn0w to jailbreak the device and install Cydia/Icy
10)Reboot with a fully working iPhone without having to restore.
It's important that the phone is plugged into iTunes, and it's important that you realize you will only have about one second before the device will automatically attempt to power itself back on while connected to your computer -- if you see the Apple logo, you didn't do it quick enough. Start over.
After installing redsn0w, I did not need to upgrade Winterboard, though the obvious four (libxml, cydia, mysql, etc.) needed immediate updates.
EDIT: Installing redsn0w blew my Cydia installed package list away so I needed to reinstall everything I had installed while purplera1ned to get it to show in Cydia, which did cause the springboard to boot in safe mode the first time I installed Winterboard, but I did a package upgrade and that fixed everything again.