If both phones have Bluetooth, you should be able to copy your contacts from the old phone to the new one. If the old phone does not have Bluetooth then you have a couple of lesser options:
1) If someone else (friend, family member) has a Bluetooth equipped phone, and they have some of the same contacts you have, you can selectively copy those contacts from their phone to your new phone via Bluetooth.
2) Send out an email to your contacts asking them to call you on your new phone. It can be a "missed call" from them. Assuming you will recognize their #, you can then save it as a new contact. Saves a little time cuz you don't have to manually enter their phone # on the contact listing.