Your contacts still should be residing safely on your computer or with your cloud service. Resynch again.
Besides i share you a article about how to transfer contacts from iPhone to computer, which can help you backup all iPhone contacts and contact photos from iPhone to your computer and keep them safe on the computer.
Good Luck. Edited by appleluntanern - 11/13/11 at 9:15pm