It looks like Alfred 2 isn't playing nicely with CCleaner.
When I set CCleaner to clear miscellaneous caches, it seems to corrupt the Alfred application cache. If I set CCleaner to ignore miscellaneous caches it doesn't seem to cause the same problem.
It's odd, the last version of Alfred didn't have this issue.