Data & Internet Doesnt Work after OS 4 update (from 3GS)

I recently updated my 3GS to the 4.0 operating system. Now after the update, I cannot use any internet necessary app (Safari, ESPN, E-Mail, etc.) unless I am on WiFi. I have restored my iPhone 2 times already, restarted my phone, reset the network settings and still NOTHING. I have full reception and the 3G logo is visible by the bars, but I cant connect to anything that needs internet. I have no problem calling or receiving text messages.

In Safari I have received this message " Safari cannot open this page because the server stopped responding"

I had previously jailbroken my iPhone with Cydia and lost the backup from before the jailbreak. I update my phone with OS4 straight from the Jailbreak.

Any suggestions? I dont know if this is an AT&T thing or if I should go to Apple on the busiest day of the year (the new 4G release).

 

If I set up new and dont restore from backup, ill lose all my contacts and I have ALOT of contacts. Any way to keep my contacts in the process??

 

What do you mean by "defined the data and mms settings"
Ive reset the network settings multiple times and messed around to see what would work (always resetting after each non-working solution)