Yes, that is what I expected. But it doesn't work on my site.
I did some further testing in the meantime, and when I change the theme to SnowFlat the voting buttons start to work (well, sort of, since the points don't seem to get applied, but at least the vote counter goes up). When I change the theme back to my own I'm back to "cannot upvote unless downvote permission applies as well". I can unvote a vote I cast while the other theme was active, though (but not re-vote afterwards).
My theme is based on your Clean Base theme and essentially just changes the stylesheet. Could that be the problem? Does Q2A 1.8.4 need changes to the PHP code in the theme?