iOS7 Contacts Have All Disappeared
Finally found the solution. If this happens to you, try turning on (or turning off/on) the iCloud contact syncing, even if you don't think you're using it.

I turned it back on (I never realized it was on) and all my contacts came back. I guess the phone was using iCloud to sync contacts all along and I wasn't aware of it.