Cingular will gladly sell you a new SIM card for a phone you purchase on ebay. If I recall they are around $20. You won't get all the numbers back that are stored in your lost phone unless you had them backed up to your computer. All that happens is in the Cingular office they just have to assign your cell number to the new SIM card. They shouldn't charge you for that service.