I'm having a very similiar issue with my iphone 3GS.
I had it on 4.1, jailbroken and installed the iPad Basband, and used Ultrasn0w on Cydia to Unlock it. I installed Ultrasn0w and rebooted the iphone - except the iphone didn't and still hasn't managed to reboot since I installed Ultrasn0w...
I don't even know if this phone still has any hope I'm so frsutrated about it! I haven't really tryed much but rejailbreaking it or rebooting it on redsn0w as well as kicking it out of recovery mode after trying to restore it with iTunes. Please help! it is repeatidly rebooting to no success and staying on recovery mode. Please help!
If you have the 4.1 SHSH backed up and saved in Cydia or TU, then I can help you. I have a 32GB 3GS on iOS 4.1 and baseband 6.15.00. JB with limera1n, and unlocked with ultrasn0w. I actually wrote myself a "restore guide" since I've bricked my iPhone a few times. Restoring back is easy since I know exactly how to restore and recover the firmware, along with my backed up data.
Add-on update: I'd be weary receiving help from someone who wrote what I did earlier... Yes, I bricked my iPhone several times, but every time it forced me to figure out why. After weeks of being an idiot, I learned how to restore my device with my right eye closed. Ye of little faith.