Network error when going overseas

[Ciel Rouge]

Wondering if anyone else had the same problem and can help. I have a locked AT&T iPhone and I took it to the UK with me over the Christmas Holiday(International roaming *was* activated with AT&T beforehand) and could not connect to any of the UK networks even though my phone detected all of them under "Network Carriers". As soon as I would pick a carrier (I tried them all) it would try to connect but after a good 10 secs I would get an error message saying "Network lost" and the "No Service" message appeared in the top left corner of the phone. I'm not sure if this is an Apple issue or AT&T issue but it's driving me bonkers as I'm going to be going backto the UK in a couple of months and would like to use the phone for texting and/or emergency calling.