try using redsn0w 0.9.6rc8 ,
then install ultrasn0w, dont reboot from the button.
leave cydia.
power off the phone.
reboot.
install carrier reset fix from cydia.
power off the phone.
boot tethered with redns0w.
by now it should work.
ive just tried this with an iPhone 3gs with the exact same problem.
old bootrom btw if thats a necessary information. (and maybe the first power off isnt needed, but hey thats the exact same way i did it).
I now see 4 bars of service at least, opposed to the "NO SERVICE" string i was seeing before
hi. i just managed to crash the phone by installing apt backup. so ill have to re run all the steps. so if i run into problems again (hopefuly not) i can give you more insight.
what did you do / what happened. i need more detailed information