Performed the upgrade, JB and Unlock successfully (using redsn0w for Windows and ultrasn0w). At this point I was happy because I checked the 3G Internet connection and it was working fine, as well as all apps using Internet connection.
Then I performed a sync with my itunes and installed several apps from Cydia (Backgrounder, Winterboard, LockInfo, SBSettings, iBlacklist to name a few) and didn't noticed any issue until I ventured out of the house and realized I had no 3G Internet connection again.
I've tried reseting the Cellular Data Network, using the right APN info from my provider and still no 3G connection. I do get the 3G little icon next to the provider name on the iphone, and also get a "Data IP Address" when I check thru SBSettings, however when I try to open any page on Safari I get "Safari cannot open the page because it is not connected to the internet". Same thing with any app, no Internet connection.
Need Help!!!!

You didn't say what version of iOS running there and what redsn0w version used to jailbreak...

Iphone 3G
Upgrade from iOS 3.1.2 to 4.0.2
redsn0w for Windows 0.9.5b5-5

Nice.

Use redsn0w 0.9.5b5-5 pointing to iOS4.0 IPSW, use lastest ultrasn0w from repo666.ultrasn0w.com, trick: keep your 3G switch OFF before start restore process.

Try use some other simcard to verify if your connection works on that sim.

Goodluck ,

That's exactly what I did. Used iTunes and restore 4.0.2 and then used redsn0w 0.9.5b5-5 pointing to iOS4.0 IPSW on the JB.
I did take the sim out during the whole process, but didn't turn the 3G off.
The weird thing is that 3G did work up until I installed something from Cydia or performed the first sync to restore my backup.
Have been un-installing some of the apps from Cydia but no luck yet.

Try it again but don't restore your previous backup.