New iOS9 Spotlight search not finding contacts
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.