I did a reset all settings to try and fix the dreaded contacts not showing up in Spotlight search on iOS9. After that, “Sign into the iTunes store” kept coming up when going to Spotlight search.
The fix was not obvious. I need to sign out of iCloud and delete from phone, then sign in again. Weird.