If it is quad band it would work for sure, tri-band it should work, but
depending if locally the 1900 frequency is supported by your carrier. Nokia
and I think Sony-E have options on their websites to sms your phone to set
it up for Cingular, I bought a Nokia 6270 sometime ago, Nokia via SMS set it
up for medianet and works fine. Cingular via customer support over the
phone talked me through setting up the local voice mail number.

I am not sure if an old AT&T sim will work in a new Cingular locked phone,
so buying one under a non-contract price may not be an option, but it's
something to look into.