On my iPhone 6 running IOS 9.1 (release 13B143), I cannot find any results when searching in either the Contacts app or in the Contacts tab in the Phone app. I have hundreds of contacts, but no matter what letter I type in the search field, I get no results. Example:

But before I started typing, I could see dozens of contacts with last names starting with "A". This is a new problem; everything was working until a week or so ago, when I first noticed this issue.

Note: this is not the same as the many questions about Spotlight search not finding contacts, such as this one. Spotlight actually does find my contacts. The Contacts and Phone app, however, do not.

How can I fix this?