If you have not already try (assuming you were backing them up to google)
menu.settings.accounts and syn.gmail.uncheck contacts
then log in to gmail on a desktop location and go to contacts, see if they are still there. sometimes you can catch it before they are deleted there.
you can also use the restore function mentioned above but do note this restores the data as it was at the point and time you pick. I would make a backup of your contacts as they are today prior to restoring from an earlier point just to be safe.
to do log in to gmail as mentioned above, click contacts, then more
and a bit of overkill...create a back up from your desktop connection, then put it on your sd card and restore it from within the phone (the steps are a little different from phone to phone but it should be open contacts.menu.import)
another neat feature I have noticed on some of the galaxy s2 variants is that you CAN back up ALL your contacts to the sim card. On my previous devices it would not allow this. You might occasionally do that for a just in case go to back up