I'm having this same issue.
This was working before Mavericks.
Let's use Recent Downloads (https://github.com/ddjfreedom/recent-downloads-alfred-v2) as an example.
I'll type "Rec", the Recent Downloads workflow displays below the Alfred prompt as before, I hit the down arrow, then enter, and at that point Alfred reverts to the default search.
In the terminal, the output of whereas ruby is /usr/bin/ruby
Thanks for looking into this!