hey guys, i had the same problem on my wife's iphone 3gs, i tried so many ways but nothing, i took it to a store and he fixed it for a 20$.. but again i had the same problem today with my iphone 3gs, but i google for a help and here is what i got and it worked perfectly :
"Use old SIM card, putting the old SIM card in the iphone (respring) then remove it and replace it with ur SIM and here it goes working again"
hope it works with u guys it worked for me.. best wishes and good luck.
Jami from lebanon