Were you set up to sync with iCloud? if so, sign in to www.icloud.com with your apple id and password, and you should have access to all your contacts.
If you were syncing with another service (Yahoo, Google contacts, hotmail come to mind), check there also.
Good Luck.