Spotlight does not seem to work in finding apps
A recent article on MacIssues suggests rebuilding the spotlight index in situations like this.

Briefly, the proposed solution is to go to the Spotlight preference pane (in System preferences) and add your disk drive to the privacy list, then remove it again.

The article also makes oblique reference to certain “Terminal-based approaches”. The obvious candidate is called mdutil. You can use the -E flag to erase the local metadata store for the named drive(s), or -i off followed by -i on to turn indexing off, then on. (Disclaimer: I have not tried this. Check the manual page.)