No search results in the Contacts app on IOS 9
I figured this out. Somehow, I had two different contact cards marked as "my" card: one named "Ed Cottrell" and one named "Edward Cottrell." I have no idea how both of them got marked as "my" card; I don't even know where the second one came from. On my phone, only one of them showed up. In the Contacts app on my Macbook, both of them appeared. Anyway, this gave me an idea that this might be the source of the problem.

I took the following steps:


Delete one of "my" cards on the Macbook.
Exit the Contacts app on my iPhone (fully, as in double-pressing the home button and dragging the app upward).
Relaunch the Contacts app on my iPhone.


At this point, the "Groups" label appeared in the upper left corner of the Contacts app. I had been seeing a circular "reload" arrow, but no "Groups" label.

Tap on the "Groups" label.
Uncheck all groups.
Tap "Done."
Tap on the "Groups" label.
Check all groups.
Tap "Done."


And now, my contacts search works again. This was a pain, but at least it's fixed.