Because your old phone was TDMA and your new phone is GSM. Cingular is moving their entire network from TDMA to GSM and as time goes on there will be less and less TDMA capacity and more and more GSM.
Wasn't your old phone a Nokia 5165? If so, poke around on ebay and get yourself a Nokia 6340i. It's GSM (actually a GSM/TDMA combo) and it fits all the same stuff as a 5165. I got my 6340i because I had a5165 car kit in my truck. You need only move the SIM chip from your current GSM phone to the 6340i and it'll work. They're quite cheap, about $20 plus shipping.
When my wife lost her fancy flip phone, I bought a new SIM from Cingular, then a rugged 6340i on ebay. I also blew $3 on some new covers so her phone would look different from mine.