There seems to be a lot less of this in Cata. Thrall admits that he's not what he could have been; Sylvie goes all Lich Queen; Varian and Garrosh have their obvious flaws; etc.
Blizz has always gravitated towards making the peacemongers infallible. Perhaps because the alternative—peacemongers making bad decisions—makes it hard to take them seriously. I'm sure they'll be less prominent in Cata, though. Still, I'd love to see a peacemonger make some really bad decision that results in the slaughter of many innocents, and a warmonger be justified as a major plot point.
It's also hard to make players believe that their leadership is basically good and fighting the good fight without a couple the-advisor-was-an-evil-dragon mind-control plot devices. And players want to feel like, on the whole, they are agents of a just cause.
Many Paladin characters do have meaningful flaws and struggles, but they may not be obvious. The Blood Elves are pretty straightforward. Remember Aldor No More? There's another. Turalyon blames himself for Lothar's death and may have led the charge into Outland more for personal reasons than for service. Uther admits that he struggled for a long time to forgive Arthas. Oh, yeah, and Arthas himself represents the best case of a fallen Paladin. Bolvar was pretty badass, but he's supposed to be a spiritual inheritor of Lothar. He represents the best we can be, which makes his death all the more meaningful.
Tirion is a bit of a Mary Sue ... and that is a major turn-off for his character. Honestly though, that's poor writing born of trying to make him a character whom everyone will like.