Issue: My iPhone 3GS was working fine prior to upgrading to iOS 4. Once I did that, I couldn’t connect to the 3G network anymore even though all the apps worked while connecting via wifi. I tried turning the Airplane Mode on and off, rebooting, etc. etc. Nothing worked. It was completely frustrating!
Fix: YMMV, as I’m on the Fido network in Canada, but this what I did. I have to do this every time there is an update as well. I went to Settings/General/Reset/Reset Network Settings Once I did this, the iPhone restarted, searched for a network, and everything worked again.
If you try this, you’re on your own, but it worked for me. Good luck!