The search sesults view is empty on a fresh install of Kubuntu 16.04. Reproducible: Always
Created attachment 98656 [details] Empty search results
Does it list applications in the main view? Or in the categories?
It does so normally. The search actually shows only plasmoids, which is somewhat counter-intuitive.
Interesting, this is because you don't seem to have access to the appstream database. Please ask your distribution about it.