Sorry for digging up a really old thread, but I wanted to clarify some stuff.
Sprint and Verizon use CDMA technology, while Cingular and T-Mobile use GSM technology. CDMA does not use SIM cards. All the info is on the phone's memory, not on any cards. The phone stores the information that it needs to access the network, and for the network to recognize it. The phone also stores all your contacts. GSM, on the other hand, uses SIM cards, which are used to do the same things.
Nextel also uses SIM cards, but a different type of card. They use iDEN technology, so the cards are the type that support that.
Cingular and T-Mobile phones can be used on each other's networks, but only if you unlock the phone. Unlocking can be done very easily and for very cheap. Some phones even come unlocked.
Sprint and Verizon phones cannot be carried over to another network. They are locked to their own network, and neither network will allow the activation of non-network phones.
You can always buy a new phone and keep the same number and service, unless you buy a phone that cannot be used on the network. With GSM networks, you can use just about any GSM phone ever sold in the U.S. With CDMA, you can only use phones sold by that particular carrier.
You might be required to change your plan and renew your contract based on what conditions you bought the phone under, but as long as it's a compatible phone, they will never say that you can't keep the same number and service provider.