Karma isn't enough. Apparently there's also an average karma per comment threshold.

The down-arrow is always displayed for me, but often the up and down-arrows have no real effect: for instance, if I upvote a comment its count goes up but after I reload the page the count is back at where it was. This is a known behavior though I don't think it's documented.