Become a MacRumors Supporter for $50/year with no ads, ability to filter front page stories, and private forums.
I'm having this problem too.
Some time they show, some time they won't.
It's a bug.
Search is enabled for contacts.
 
Here's what I did. Switch off contacts via iCloud, when it asks if you want to keep or delete contacts from you phone, I chose "delete" (my contacts are backed up to the cloud). After I enable the contacts in iCloud and it works!
 
Register on MacRumors! This sidebar will go away, and you'll see fewer ads.