I also had this problem since I upgraded my 3GS on Thursday. I did a full restore from a backup, and my internet still wasn't working. Like others, my WiFi was working though. From information I gleaned, it's either corrupt APN settings, or I think in my case (I checked and my APN settings were blank), that updating it just deleted them altogether. On your phone tap Settings > General > Network > Cellular Data Network. If it's all blank like mine, you need to find out your carriers APN settings and input them. Restart the phone, and it should work.