My iPhone was jailbroken and unlocked with firmwire 4.2.1
I thought I stored my SHSH in cydia since I saw it on the main page of cydia has mentioned something like "SHSH: ios 4.1, 4.2.1, 4.2b3"
I wanted to reset everything on my phone, so I simply pressed "Error my iphone and data" under setting on my iPhone.
My iPhone stuck in the middle when restoring, so I had to restart my iPhone by holding power+home buttons.
Then, my iPhone could not start, and stuck in the recovery mode.
Now I tried to use TinyUmbrella, I wasnt able to retrieve my SHSH on server. I tried to use the legal way to restore my iPhone using iTunes. I always got a message of 1015.
I tried to kick my iPhone out of the recovery loop wit TinyUmbrella and iReb. My iPhone did reboot but it went back to the recovery mode again.
I had gone through this exact same situation. Running 4.2.1 on iPhone 3g, BB 06.15. I had wanted to sell it, so I chose the option to "Erase data and settings." In the middle of the process, the phone got stuck on the pineapple icon. I put it into Recovery Mode, where it remained for the last few days.
I was finally able fix it by doing this:
1) Put the phone into DFU mode using pwnagetool
2) Go into iTunes and hold down shift when clicking restore
3) Restore to a customized firmware. I built mine using pwnagetool, combining the 3g 4.2.1 ipsw with the ipad bb 06.15. There are instructions online for that.
Pwnagetool is your best friend in this situation. Hope this helps, good luck!