Here's a complete and comprehensive list (with maps) of GSM coverage around the world (you're welcome in advance ):

http://www.gsmworld.com/roaming/gsminfo/index.shtml

It's proved incredibly useful for me to determine if my GSM phone will get coverage (roaming or not) wherever I am in the states or internationally. It's ATT, still, because I refuse to be bullied into Cingular's plans when my ATT plan of old suits me just fine. But note, it is still GSM.

You'll have to look at the specs of your phone to see what coverages it gets you (if you go for a GSM, which I recommend). Most newer GSM phones sold by ATT/Cingular are at least Tri-Band (850Mhz/1800/1900). This is great, except for the parts of the world that use GSM 900, which is a lot of central America and eastern Asia (outside the big cities), in addition to the really rural parts of the U.S. or if you're in a basement. Alternatively, you could get a quad-band phone from Cingular (you'd have to change to a Cingular plan if you're still on an old ATT plan) and that quad-band phone will work almost anywhere in the world without any need for a SIM, etc. Roaming can be expensive, though. Over $2/min in some places.

As for nation-wide coverage...yes, Cingular's not the best. Your best all-in one solution is to get a quad-band phone so that if you can't find an 850/1800/1900 signal, you might be able to pick up that 4th band (900Mhz). Although, places like northern Iowa (from experience) have no GSM coverage whatsoever, so any GSM phone, regardless of service provider, will not work.

Other than a satellite phone, I don't think there's one phone that will work everywhere. So, you'll have to take a look at coverage maps and phones you like (i suggest a quad-band for the OP) and find the best comprimise. I don't think you'll be happy down the road if you stick with an old analog phone (TDMA) or get a competing phone to GSM (CDMA). CDMA is on its way out, as GSM is going to be the prevailing force here soon as the U.S. tries to catch up with the rest of the world in using a unified cell technology.

/phew. Good luck.