I'm running into a similar issue. I'm also on 10.8 (on a beta seed to be exact) and running on 2.0.3.
There are some applications that Alfred cannot find in /Applications such as Transmit, Notes, Calendar.. This seems to be somewhat random.
I've tried rebuilding OS X metadata and cleared Alfred's cache, and also the "reload" command suggested above, but it doesn't fix the problem. Spotlight can find these apps just fine. Oddly enough, after relaunching Alfred, it can find Transmit but still can't find Notes or Calendar.
I found a few error messages in Console.app generated from Alfred 2, where an exception is raised. These messages occurred several times yesterday. I'm not sure if this is related to the problem at hand, but it's probably worth mentioning: