There are different wireless network technologies in the US.
Cingular/ATT, are TDMA/GSM network technology. I believe T Mobile is as well.
Verizon and Sprint are CDMA network technology.
Nextel had its own network with its own technology (can't recall the name of its technology just now); interesting that they are merging with Sprint now.
I am not sure which network Alltel is on; I think it is TDMA/GSM but that is a rusty guess because I have not been in wireless for a few months.
Even though Verizon and Sprint have the same type of networks, that does not mean they automatically roam on each other's network--that is only if they do not already have their own towers in the area. So, in a city like Denver, Sprint may be the best performing but in NY Verizon may be the best. It depends on where they companies have invested in towers. Where they have not made investments, they then make roaming agreements with the carrier in the area that has the same technology. So, say Verizon had lots of towers in Birmingham, Alabama and Sprint did not, then Sprint may pay Verizon to 'roam' on their network. But Cingular/ATT does not because it is a different network technology.
So if someone's Verizon phone works in SoWal, that does not mean the Cingular phone would work as well or vice versa because of the network technology.
Other wireless brands like Virgin just pay to use some other carriers network, like Sprint. So when you see Disney come out with kids' phones , they are not creating a Disney network, just a Disney brand phone service that uses someone else's network.