If you have verizon you can set up your phone to automatically backup to their website, and then you can manage your contacts online and send them to your phone (or a new phone).
edit- just noticed you had a sim card, so I assume you dont have verizon.