if you had any settings you wanted to retain from before you reinstalled (eg photos taken, SMS history, application high scores in games, call history etc) then these are contained in the backup that iTunes *should* have made the last time you synchronised the phone before you restored.
If any of this data is important to you, then you should make a backup of the backup straight away.
After that, you have two options:
Sync the backup back to the phone - this is the simplest but *can* reintroduce unwanted junk and can cause poor battery life/stability issues (less likely if you don't re-jailbreak).
Set up as new, then use a backup extraction utility to extract the key files/folders you want and then re-jailbreak. Install OpenSSH and use SFTP to copy the files/folders you want to restore to the phone.
Thanks again for your tremendous help. I managed to unfreeze from apple logo, install custom ipsw, jailbreak and unlock - and now have a working phone. Here are the steps I followed:
Phone: iPhone 3GS, iOS 4.3.3, baseband 5.16.02
a) Jailbroke first with jailbreakme.com but then learnt I needed to upgrade baseband to 6.15 iPad version
b) Saved my SHSH blobs with iFaith - please make sure you save your SHSH blobs with iFaith or some other reliable tool before you mess around with redsn0w or anything else.
c) I then ran redsn0w_win_0.9.6rc16 with two boxes checked: Install Cydia and Upgrade Baseband to iPad v. 6.15
d) Seemed to work okay. Gave me a working iPhone home screen. I had two installations of Cydia, one from jailbreakme.com and one from redsn0w.
e) When I opened Cydia from redsn0w, I got a bricked / frozen phone stuck on apple logo.
Here's what got me back to a unfrozen, custom 4.3.3 IPSW on baseband 6.15, which is now jailbroken and unlocked.
1. Charged it to make sure there was enough battery, just in case. Connected data cable to iPhone and Windows 7 laptop.
2. Ran iFaith v.1.3.2 to Build *signed* IPSW w/Blobs - I was fortunate enough to have saved my SHSH blobs before I did the first version of redsn0w
3. Pointed iFaith to my saved SHSH blobs (*.ifaith file extension) and iOS iPhone2,1_4.3.3_8J2_Restore (original version from Apple)
4. Followed on-screen instructions
5. iFaith generated a custom IPSW - 000002C31119C34D_iFaith_iPhone_3GS-4.3.3 (8J2)_signed 436.5 MB file - which it saved on my desktop. iFaith did not mess with the upgraded 6.15 baseband at all - so this works great even if you have a bricked iphone that is on the 6.15 baseband.
6. iFaith also put my iPhone in a mode where it could be restored with iTunes
7. When iTunes recognized the phone, I held down the SHIFT button (on Windows 7 laptop) and clicked Restore. This opened up a window which let me browse for the custom IPSW - 000002C31119C34D_iFaith_iPhone_3GS-4.3.3 (8J2)_signed - which iFaith saved on my desktop earlier.
8. iTunes did a fresh restore using the custom IPSW
9. Upon completion, iTunes asked me if I wanted to
Restore as a new iPhone
Restore from the backup of my old iphone
I checked online and iphone dev team had a note that said Restore as a new iPhone - which is what I did.
10. I now had a custom 4.3.3 IPSW on 6.15 baseband, but not jailbroken
11. I ran the new redsn0w_win_0.9.9b1 (thanks to a tip from Olethros) - and only did Jailbreak - jailbreak and install Cydia
12. Followed redsn0w's on-screen instructions... it put cydia on my iPhone and I now had a jailbroken iphone
13. Installed cydia, went to Manage at the bottom, checked Sources. It had ultrasn0w there. I installed ultrasn0w... (there are clear videos and instructions online that explain this) it did its thing... and voila - worked beautifully... so I now have a 3gs, custom iOS 4.3.3, iPad 6.15 baseband, jailbroken and unlocked. I tried it with an international SIM card and it let's me call - no problem.
14. I am told that I cannot put in another AT&T SIM card and use this as a regular phone in the US because AT&T apparently recognizes this sooner or later and demands that you get a data plan or threatens to cancel your voice service too - this really sucks. Does anyone know any better??
Finally, thanks to Olethros for his wonderful advise - was a superb guiding hand for my storm in a tea cup.
Good luck with your phone!