Who is your carrier? Are you roaming, or have you installed a local micro-sim in your phone? If so, who is the carrier whose sim you have in your phone now?
Not all 3G networks are compatible with the iPhone. T-Mobile's U.S. network is one example. What network are you locked on to at the moment? Check to see if it is one of these: http://support.apple.com/kb/ht1937
If it is NOT one of the carriers on that list, you'll need to contact the carrier you're on to find out what, if anything, you can do to get it working.