I know you've sorted this... but thought I'd add my 2p to the conversation, as there are a few things you can do to make life easier here..
You can Sync your contacts to your PC via iTunes. You need Outlook installed or Vista with Windows Contacts and Mail. With the phone connected, you can chose where to Sync this information to via the information tab (from memory, correct me if I'm wrong). This will then keep a copy on your PC and you can repeat the process in reverse with a new iPhone or any other phone that can sync with Outlook etc.
Another option is to use one of the various online 'Cloud' services. My three recommendations are MobileMe from Apple, Google Mobile Sync and ZYB.com. All three allow you to Sync over the air (OTA) and have a backup of your contacts and calendar online.
MobileMe is setup from within the phone with presets already stored to make it easy to configure. This allows Push email and synchronising. This is a subscription service so there is an ongoing cost associated, but there is also numerous other items in the bundle such as photo hosting, web storage space and an awesome feature that lets you make your phone beep if you're lost it. But you can only lose it within ear shot....

There is a free trial of MobileMe available to try before you buy.
Google Mobile Sync is free and syncs your calendar and contacts to your Googlemail/Gmail account. Fantastic if you use this service anyway. It uses Microsoft Active Sync to connect and sync and also supports Push for contacts and calendar only.
Googlemail is setup as a separate profile.
ZYB.com has been around for a while and is growing to become a social networking site, but my only interest is it's free online Contacts and Calendar Sync. Once you have created an account on the ZYB website, you download the free App from the App Store, sign into it and Sync.
There are numerous other options around I've no doubt, but I can only speak of what I know.
I personally use Google and ZYB.com - Google because I use Googlemail and Calendars. ZYB.com because it supports the vast majority of mobile handsets around, so I can easily get my contacts and calendar back on any other handset should I lose it or change phones.
So my advice is even if you have sorted your problem now, sign up to one of these services and get into the habit of synchronising your content, so you always have an online backup.