I think this whole "utilitarian vs. deontological" setup is a misleading false dichotomy. In reality, the way people make moral judgments -- and I'd also say, any moral system that is really usable in practice -- is best modeled neither by utilitarianism nor by deontology, but by virtue ethics.

All of the puzzles listed in this article are clarified once we realize that when people judge whether an act is moral, they ask primarily what sort of person would act that way, and consequently, whether they want to be (or be seen as) this sort of person and how people of this sort should be dealt with. Of course, this judgment is only partly (and sometimes not at all) in the form of conscious deliberation, but from an evolutionary and game-theoretical perspective, it's clear why the unconscious processes would have evolved to judge things from that viewpoint. (And also why their judgment is often covered in additional rationalizations at the conscious level.)

The "fat man" variant of the trolley problem is a good illustration. Try to imagine someone who actually acts that way in practice, i.e. who really goes ahead and kills in cold blood when convinced by utilitarian arithmetic that it's right to do so. Would you be comfortable working or socializing with this person, or even just being in their company? Of course, being scared and creeped out by such a person is perfectly rational: among the actually existing decision algorithms implemented by human brains, there are none (or at least very few) that would make the utilitarian decision in the fat man-trolley problem and otherwise produce reasonably predictable, cooperative, and non-threatening behavior.

It's similar with the less dramatic examples discussed by Haidt. In all of these, the negative judgment, even if not explicitly expressed that way, is ultimately about judging what kind of person would act like that. (And again, except perhaps for the ideologically polarized flag example, it is true that such behaviors signal that the person in question is likely to be otherwise weird, unpredictable, and threatening.)

I'd also add that when it comes to rationalizations, utilitarians should be the last ones to throw stones. In practice, utilitarianism has never been much more than a sophisticated framework for constructing rationalizations for ideological positions on questions where correct utilitarian answers are at worst just undefined, and at best wildly intractable to calculate. (As is the case for pretty much all questions of practical interest.)