Are you trying to access your search through the blue menu bar, Search > Unanswered Threads? That one just worked for me.

Or are you using Advanced Search and specifying [At most] [0] Replies? That one just worked for me too. It seems to be a different search, though, and to show results in a different format, so whatever affects one might not affect the other the same way.