One idea that I have been toying since I read Eliezer's various posts on the complexity of value is that the best moral system might not turn out to be about maximizing satisfaction of any and all preferences, regardless of what those preferences are. Rather, it would be about increasing the satisfaction of various complex, positive human values, such as i.e. "Life, consciousness, and activity; health and strength; pleasures and satisfactions of all or certain kinds; happiness, beatitude, contentment, etc." If this is the case then it may well be that horribly malevolent preferences, such as those the Nazis in this thought experiment exhibit, are simply not the sort of preferences that it is morally good to satisfy. Obviously judging which values are "worthy" to be increased is a difficult problem that creates huge moral hazards for whomever is doing the judging, but that is an implementation problem, not a problem with the general principle.
If this line of reasoning is correct, then the reason that preference utilitarianism seems so intuitively persuasive is that since most of our moral reasoning deals with humans, most of the time maximizing whatever a human being prefers is pretty much guaranteed to achieve a great many of those human values. For this reason, "human values utilitarianism" and preference utilitarianism generate the same answers in most real-world scenarios. However, there might be a few values that human beings are theoretically capable of having, but aren't morally good to maximize. I think one of these morally bad preferences is sheer total malevolence, where you hate someone and want to hurt them as an end in itself.
This theory would also explain why people feel that it would be a bad thing if an AI were to kill/sterilize all the human beings in existence and replace them with creatures whose preferences are easier to satisfy. Such action would result in increased preference satisfaction, but they'd be the wrong kind of preferences, they wouldn't be positive human values. (Please note that though I refer to these as "human values," I am not advocating specieism. A nonhuman creature who had similar values would be just as morally significant as a human)
This gets a little more complicated if we change the thought experiment slightly and assume that the Nazi's Jew-hatred is ego-dystonic rather than ego-syntonic. That is, the conscious rational, "approving" part of their brain doesn't want to hurt Jews, but the subconscious "liking" parts of their brains feel incredible pain and psychological distress from knowing that Jews exist. We assume that this part of their brain cannot be changed.
If this is the case then the Nazis are not attempting to satisfy some immoral, malevolent preference. They are simply trying to satisfy the common human preference to not feel psychological pain. Killing the Jews to save the Nazis from such agony would be equivalent to killing a small group of people to save a larger group from being horribly tortured. I don't think the fact that the agent doing the torturing is the Nazis' own subconscious mind, instead of an outside agent, is important.
However, since the Nazis' preference is "I don't want my subconscious to hurt me because it perceives Jews," rather than "I want to make the statement 'all Jews are dead' true" there is an obvious solution to this dilemma. Trick the Nazis into thinking the Jews are dead without actually killing them. That would remove their psychological torment while preserving the lives of the Jews. It would not create the usual moral dilemmas associated with deception because in this variant of the thought experiment the Nazi's preference isn't to kill the Jews, it's to not feel pain from believing Jews exist.
Of course, if you have the option of lying, the problem becomes trivial and uninteresting, regardless of your model of the Nazi psyche. It's when your choice requires to improve the life of one group at the expense of another one suffering, you tend to face a repugnant conclusion.
This is based on a discussion in #lesswrong a few months back, and I am not sure how to resolve it.
Setup: suppose the world is populated by two groups of people, one just wants to be left alone (labeled Jews), the other group hates the first one with passion and want them dead (labeled Nazis). The second group is otherwise just as "good" as the first one (loves their relatives, their country and is known to be in general quite rational). They just can't help but hate the other guys (this condition is to forestall the objections like "Nazis ought to change their terminal values"). Maybe the shape of Jewish noses just creeps the hell out of them, or something. Let's just assume, for the sake of argument, that there is no changing that hatred.
Is it rational to exterminate the Jews to improve the Nazi's quality of life? Well, this seems like a silly question. Of course not! Now, what if there are many more Nazis than Jews? Is there a number large enough where exterminating Jews would be a net positive utility for the world? Umm... Not sure... I'd like to think that probably not, human life is sacred! What if some day their society invents immortality, then every death is like an extremely large (infinite?) negative utility!
Fine then, not exterminating. Just send them all to concentration camps, where they will suffer in misery and probably have a shorter lifespan than they would otherwise. This is not an ideal solutions from the Nazi point of view, but it makes them feel a little bit better. And now the utilities are unquestionably comparable, so if there are billions of Nazis and only a handful of Jews, the overall suffering decreases when the Jews are sent to the camps.
This logic is completely analogous to that in the dust specks vs torture discussions, only my "little XML labels", to quote Eliezer, make it more emotionally charged. Thus, if you are a utilitarian anti-specker, you ought to decide that, barring changing Nazi's terminal value of hating Jews, the rational behavior is to herd the Jews into concentration camps, or possibly even exterminate them, provided there are enough Nazi's in the world who benefit from it.
This is quite a repugnant conclusion, and I don't see a way of fixing it the way the original one is fixed (to paraphrase Eliezer, "only lives worth celebrating are worth creating").
EDIT: Thanks to CronoDAS for pointing out that this is known as the 1000 Sadists problem. Once I had this term, I found that lukeprog has mentioned it on his old blog.