While traveling around Southern Spain in April 2013, I had a very difficult time getting a data connection on my iPhone 4S. The phone was purchased in the US with locked service from AT&T. Prior to my trip, I purchased the Global Data, Phone, and Messaging services from AT&T so I was not expecting any troubles.
The phone automatically connected to the Orange network and most of the time indicated a 3G connection. Voice calls worked Ok, and so did text messaging, however, Internet data access was not working (for example, no email access and no Web browsing) and SMS messaging with attachments (such as photos) was not working.
To fix the problem I tried to change carriers (by turning Automatic off from the iPhone’s Settings->Carrier menu) but no other carriers appeared in the list; the phone was searching for carriers but only Orange appeared. Ultimately I left the phone searching for carriers for several minutes (maybe as long as 3-4 minutes) and several other networks were found. Selecting “vodaphone ES” and the data services on the phone started working reliably.
Remember to switch back to automatic carrier selection after the trip.