i think it always does. if it was the actual murder part of a murder that people didn't like, they would unequivocally oppose capital punishment, because by its nature it involves murder. they're okay with the bit where somebody kills somebody else; they just don't like that their mental balance has been thrown, and they can resolve that dissonance by disposing of the problematic individual.
this has the nasty side-effect of establishing that it really is okay to murder somebody, as long as they're evil enough... and since 'evil' is subjective, we get everybody demanding everybody else be beheaded. once in a while, somebody decides to "take justice into their own hands", which is where murder comes from in the first place.