i had an issue today w/ my iphone 4. I would get 'no service' on 3G, but full bars and internet/sms functionality when 3G turned off in settings/network, and phone on Edge. 3 restarts later, seems to work fine. Weird.
I thought the phone auto-switched to Edge if 3G was unavailable?