Are you sure you chose the 3G option?
Your phone will most likely have two options as shown in the following screenshot.
Enable 3G
Cellular Data (shown as the British English equivalent "Mobile Data" here)
The first option will disable the 3G network and only enable your carrier's 2G network (which may provide GPRS, EDGE or 1xRTT data). If there's no 2G signal or the network doesn't support data then you wont be able to use it in the way that you want to.
What do you see in the top left of the phone? Your phone will show a different symbol for each type of network:
http://support.apple.com/kb/HT1976