You should check out our extensive post on lost contacts in iOS 5. All the same approaches still apply in iOS 6 (if you let me know if it helped, I’ll mark iOS 6 next to entries that help iOS 6 users).
UPDATE: The TamTam Solution to iOS Lost Contacts
A comment by “TamTam” on this page has proven very helpful for a number of people, follow these steps:
- Connect iPhone to iTunes
- Go to iPhone Summary
- Switch from “Back up iCloud” to “Back up to Computer“
- Go to info tab, at the bottom (in advanced settings) “Replace info on this iPhone“
- Click on Contacts