We have a half dozen iThings in our household. What worked for us consistently is unchecking Applications, exiting the menu, pull the shade down as if to search (on the home menu), then clicking Applications on again. It should index and search fine after that. At least it did for us.
You win! Thank you!!!