Not because people who like high taxes necessarily have to oppose the death penalty.

Ok, we actually disagree then. I think that progress in the progressive sense is real, that most of today's politics is a product of historical/technological/etc. forces and more-or-less inevitable. (If I had to guess why the US is different from Europe I'd say it's largely an artifact of which groups of people originally settled there, and I expect the US to become more European in the future). I predict that even in legislatures far away from Europe we'd observe a correlation between support for high taxation and opposition to the death penalty, and that more generally if we did a NOMINATE-style analysis we'd find that positions on many issues were largely explained by a single axis of variation, and the list of things I mentioned would be at one end of it.

Or that humans are not generally naturally anything to the exclusion of everything else.

Sure. I'm not arguing that we're naturally virtue ethicists or anything. But I don't think utilitarianism is an adequate description of intuitive human morality (even American morality). Perhaps the fat man in the trolley problem is a better example; while there are no doubt many clever arguments that people are being utilitarian via some convoluted route, it's not the result we would naturally predict utilitarian thinkers to come to.

Of course, in the limit, everything is utilitarian--people in Europe may get displeasure from using the death penalty the same way they get displeasure from bad-tasting food. Is someone who avoids bad tasting food for food that costs more a utilitarian, because pleasure from food taste is a form of utilon?

I understand utilitarian to mean someone who tries to maximize some pseudo-economically consistent objective function of the external world. If someone assigns different values to actions that have the same result but get there by different paths, or evaluates a future state differently depending on the current state of the world, or believes that the same action could have a different moral value depending solely on the internal state of the person performing it, then they're not a utilitarian.