New iOS9 Spotlight search not finding contacts I've just upgraded to iOS 9, and the new Spotlight search isn't finding contacts for me - it sometimes finds contacts, but not the one I'm searching for.

I've turned off every app in Spotlight search, except Contacts, so as not to muddy the waters.

Example: I have a contact named "Fred Jones".  He's the only contact with the surname Jones.  I swipe down or right to get the spotlight search, and start typing jones one character at a time.  When I type "j" I get

TOP HITS
Jane Airy
CONTACTS
Abbadab Fabrics
Dan Anderson


When I type the "o" I get

(nothing)


I.e. no search results.

Both Abbadab Fabrics and Dan Anderson do have a "j" somewhere in some field - but so do lots of other contacts.

I've tried typing "Jo" but same results.  Obviously, this used to work in ios8.

Further details in response to questions: I'm on the released iOS 9 build (13A344), not any developer or other pre-release. I only have one account syncing Contacts - Google Sync. There's plenty of storage available: 11.0GB out of 15.2GB.
I tried two fixes, and this one seemed to work after playing around with it for a while:

Fix #1 (didn't seem to work, but may have helped)


Turn off all the Spotlight switches in Preferences > General > Spotlight.
Do a hard reset by pressing and holding the Home button (big circle below the screen) and the Sleep/Wake button (on top of the iPhone) simultaneously.  
Hold both buttons until the screen goes black, and then release when you see the Apple logo.
After restart, turn on the Contacts switch in Preferences > General > Spotlight.
It may take a few minutes, or half an hour for Contacts to show in Spotlight search.
Turn on other Spotlight switches after Contacts begin to show in Spotlight searches.


Fix #2


Open the Contacts app, tap your own contact... Then Groups will display in top left. Tap Groups in the top-left corner, then Hide All Contacts or show all contacts. One of them may default. Tapping just toggles back and forth between the 2 options. The IOS 9 update may have defaulted your option to Hide All which may be the only issue.
Tap Show All Contacts.


This didn't immediately work for me, but then I tried only showing iCloud contacts, and not Facebook contacts, and then it started to work.  However - I noticed some contacts starting to appear after a search, which is when I tried this in the last sentence.  It may very well have been the first fix that solved this, and it was just a matter of waiting for it to work.

Try both, and also showing different contacts groups, then quitting the contacts app, then hiding and showing again.