Oh, then yours are GSM too? laep's post made me think they were locked in CDMA
Yeah, sorry about that. iPhones here are GSM, too, on AT&T. And their radios don't work on the same GSM frequencies as T-Mobile USA - though they do work on T-Mobile in Germany, go figure.
Sprint, Verizon, US Cellular, and Alltel are CDMA. AT&T and T-Mobile are GSM. Others I've not had personal experience with (and am too lazy to look up).
Basically, if you want an iPhone in the US, you're stuck with AT&T, one of the crappiest providers here.