I have an iPhone 3G on Baseband 6.15. It was running 3.1.3 but I asked my sister to plug it in and charge. When she did, she also decided to update it via itunes when the popup came up.
Needless to say, this ****** it up and now it's stuck in restore mode. I've tried using tinyumbrella to kick it out but unfortuantely it just turns off, and when I turn it back on it's still in restore.
Your iphone is now at fw 4.2.1, run itunes : shift + restore to 3.1.3, activate it with official sim, and go to jailbreakme.com from safari on your iphone to do the jailbreak again. Unlock with Ultrasn0w to unlock.
Basically, I downloaded the 3.1.3 firmware and shift+clicked in itunes to restore to that. It worked, but I was stuck in the emergency calls mode. I don't have a sim to activate with, so I downloaded sn0wbreeze 1.4, created a custom firmware using the 3.1.3 ipsw, used ireb to enter pwnd DFU mode and then shift+clicked in itunes to restore to the custom firmware. After that it worked flawlessly.
I had some trouble finding Sn0wbreeze 1.4 online, so if you want me to upload it or the 3.1.3 custom firmware then send me a PM.