Hello, my problem seems to be almost the same.
I have got a iphone 3gs. My sister made it jb once by a professional, so I don't have informations about it.

When she gave it to me, I tried to delete all personal informations. That destroyed the firmware. I don't know which firmware it was, and I am not sure tho one I should install.

I tried to use redsnow (with a firmware called iPhone2,1_4.3.4_8K2_Restore) to jb it, but it stops in exploiting limera1n (although I launch it in XP sp2 mode and by the administrator)

I tried to restore with tinyumbrella and a firmware called iPhone1,2_4.2.1_8C148_Restore, but it gives me error 1604. Tinyumbrella says shsh save is valid, but I can't find files in the .shsh directory.

I also tried others tools like iReb, with a custom firmware based and that previous firmware.

My guess is that I should first know which firmware I have to use. My final goal is to have a jb phone.

Other informations : windows7, itunes 10.5.3.3. I could post logs, but there are too many of them. I'll be able to give the ones we nee.

Thanks for any help !