This happened to me just now.
iPhone 4s - iOS 5.1.1.
Haven't upgraded to iOS 6, since I need the old maps app, and the Google Maps app isn't available in my country's app store.
Apps kept closing out on me, so did a hard restart, then all contacts just disappeared. Except for the contacts in the 'Favorites' tab - the names got wiped out, but the numbers are still there. But everything in the 'Contacts' tab was wiped out - names and numbers.
Have never used iCloud, in fact I just turned it on just now - the first time I 'Accepted' the terms and conditions was just a few mins ago.
Have never backed up to iTunes either, I deleted it from my desktop immediately after first using it. Or rather, after first trying to use it.
Funny thing is, if I do a search for a contact in the "Search iPhone" page - as long as they still have messages on my phone, then they still show up with their names on search - so they're still in there somewhere.
However, if I open Messages directly, the names don't show up - only in search.
Extremely frustrating. I'd say this is almost as bad as the "sending SMS's to the wrong person" screw-up that happened with Android.