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.