I lost all mine as well, but if you go into favorites or recent calls they are still there. I went to my favorites, clicked arrow to see contact, clicked on edit. Made a change then saved it. Went back to contacts and they were all back.
If you have a backup on iTunes, you can restore to it by just on your phone going into Settings > General > Reset > Reset all content and settings. Then when it reboots, walk it through, until you get to the restore from iTunes part.
Again, only do this if you have a backup.
If you hit restore on iTunes and it asks you to backup, you can say no since your phone doesn't have any data on it now, and after it restores, it should give you the option to restore from one of your backups.