Do you have Microsoft Outlook on your computer? If so, you can go into iTunes and tell it to back your contacts onto Microsoft Outlook. However, the best way to backup contacts IMO is through Gmail. If you don't already have a Gmail account, then set one up. Once you set it up, follow the steps that Google gives you to set up the Microsoft Exchange account on your iPhone for Gmail. It's actually quite easy. After you set it up, then your contacts, calendar, and email are all pushed between your Gmail account and your iPhone. It's awesome. Let's say you run into an old friend one day, and you put their phone number in your phone, within minutes it's pushed on to your Gmail account online.
So, after everything is backed up online with Gmail, you can do a restore on your phone. Once the restore is done, go back and set up the Microsoft Exchange for Gmail and all your contacts and calendars come right back to the phone. That's how I do it and it's awesome. Makes everything a lot easier, IMO. Regardless of what you do, good luck with it.