What makes the fact that Barzan Ibrahim al-Tikriti was decapitated so disturbing? (I'm assuming others were disturbed. If you weren't, you'll disagree with nearly all of this post.) Here are three candidate explanations:
1) Coming so close on the heels of the taunting at Saddam's execution, the botching of al-Tikriti's execution will likely fuel suspicions among Sunnis in Iraq and beyond that the Shiite-led government is deliberately abusing its power to humiliate Sunnis. This in turn will further fuel sectarian violence.
2) Decapitation is a cruel method of execution. Although the guillotine was promoted in its day as humane, there is plenty of anecdotal evidence that the severed head sometimes remains alive for a small period. This is certainly one of the reasons why the hangman is supposed to try to avoid decapitation.
3) Decapitation has been used by terrorists in Iraq and elsewhere as a particularly brutal form of murder. The accidental decapitation of a murderer like al-Tikriti is of course not as revolting (to a person holding reasonable moral views) as the deliberate beheading of an innocent like Daniel Pearl, but the former nonetheless evokes the latter.
I think all of these concerns are in play here, but I also think there's a primal revulsion that goes beyond these particular consequences. One possibility is religious. Orthodox Jews oppose autopsy on the ground that when the Messiah comes, the dead will be resurrected bodily. Muslims permit autopsy if strictly necessary but would certainly regard unnecessary decapitation as profoundly disrespectful. Nonetheless, I don't think religious feelings explain the revulsion. For one thing, there's my own intuition; I'm not religious but I find the prospect of decapitation more revolting than other methods of execution, even controlling for pain (to the extent that such a thought experiment is possible). Moreover, unless one holds the view of bodily resurrection, religious convictions ought to make one care LESS about the body than otherwise: the immortal soul, in such views, is what matters.
So, assuming that I'm correct that there is a residual unexplained revulsion here, I don't have an explanation for it. My own subjective report is that this is something on the order of the revulsion against cannibalism. That revulsion probably evolved as a defense against the spread of prion disease. (See Chapter 13 of The Family that Couldn't Sleep, by D.T. Max, for a fascinating account.) Could the revulsion against decapitation be rooted in the same period of pre-human history? We know that brains are among the most infectious portions of cows and sheep infected with BSE and scrapie, respectively. Perhaps before pre-humans learned not to eat the corpses of one another, they learned not to eat their brains, which would have been facilitated by a taboo on decapitation, one that remains with us to this day. A just-so story, I freely admit, but the closest thing to an explanation that I've got.