I was having this exact issue. While fiddling with something else, I happened to have mail.app open on one of those empty smart folders in the background, and did this from the terminal:

    sudo mdutil -i on /

Now mind you, it was _already_ enabled. I had previously tried forcing reindex (-E) but that did nothing. No clue why setting 'enable' _again_ made any kind of difference, but suddenly my smart folders sprang to life. I will keep an eye on it, and see if it keeps working properly.