I might have missed something obvious somewhere, but I've been going round in circles not knowing how to get any results when using the toolbar search facility. What made it worse was that the advanced search worked fine.
However after much searching I finally stumbled on the fact that new users, events, groups, etc would appear, it was just the users already on the system that weren't appearing. So clearly something was working.
At this point I started tracing through the code and eventually hit a reference to #__finder... et viola it all made sense!
If you aren't seeing what you expect, then try running the Smart Search (components) Indexer
At least for us, this worked, we can now see suggestions and we are happy. Hopefully this might help someone else as blind or confused as I was.