If the Nazis are unable to change their terminal values, then Good|Nazi has a substantial difference compared to what we mean when we say Good. Nazis might use the same word, or it might translate as "the same." It might even be similar along many dimensions. Good|Jew might be the same as Good (they don't seem substantially different then humans) although this isn't required by the problem, but Good|Nazi ends up being something that I just don't care about in the case where we are talking about exterminating Jews.
There might be other conditions where Good and Good|Nazi overlap, and in those cases I probably would agree that the Nazi should do the Good thing, which would also be to do the Good|Nazi thing. But I don't have any reason to favor Good|Nazi over Good, and so where they differ (the extermination of Jews) I am unmotivated to defend or even to allow the Good|Nazi point of view to have a say in what is going on.
You indeed needn't care about "good|Nazi", but the important question in this hypothetical is whether you care about "happy|Nazi" or "suffer|Nazi". I don't care much whether the outcome is considered good by someone else, the less so if that person is evil, but still it could bother me if the outcome causes that person to suffer.
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.