Now, I'll be honest; I've never played a Paladin in anything but Blizzard games. My understanding of what a Paladin is, is based solely on Blizzard's interpretations. However, when I logged in my Paladin after this last patch, I was struck by how very different he feels from his original incarnation.
I started World of Warcraft back in the Vanilla Beta, and I always played a Paladin. I was a huge fan of Uther the Lightbringer (and Arthas, of course), and I just knew Paladin was going to be the Class for me. They were more rugged than Priests, yet more stoic than Warriors; to me, they were the perfect Class. I was also a huge fan of Diablo II, so that certainly helped make the decision.
Of course, the Class was also boring as hell to play back then; I don't think anyone could legitimately argue otherwise. They had some amazing strengths, but as the old saying goes: "It's like playing God-Mode, but you're playing a pacifist god".
However, the Class also had a great deal of flavor.
Any true Paladin remembers acquiring his or her Verigan's Fist back in the day, or obtaining your Resurrection spell in Elwynn Forest. And obviously, the Charger quest-chain was a whole adventure unto itself. But the things I'm talking about go far beyond that.
First off, let's look at the Paladin dress-code; honestly, most of the time Paladins looks like "Armored Clerics" these days. More than that, most (though luckily, not all) of their armor lacks any sort of "Knightly" attributes, or even references to the Silver Hand. I understand that Tauren can play Paladins now, but they should have to adhere to the Class's history, not force the rest to abandon theirs.
Secondly -- and this will probably sound incredibly shallow or petty at first -- is the name and icons of their Abilities. Everything is Yellow/Gold. To me, I just can't get over how strange that part is. I may very well be alone here, but to me, it speaks volumes about deeper-lying issues.
Back in Warcraft III and early-WoW, the Paladin was very much a battle-hardened character, not so distant from the Warrior, save for his faith. Over time, it feels like the image of the Paladin has gradually shifted to be someone whose armor is more ornamental than anything. They project the image of a character who is nothing without his faith, as opposed to a character whose faith is but one facet of his character.
Finally, there is the core of what made a Paladin a Paladin in previous Blizzard games; Group-utility. Now I'm not going to pretend like Auras were ever "fun" abilities to use, but they were absolutely a part of the character. I still remember seeing that Devotion Aura graphic in Warcraft III (in truth, I was always disappointed the visual wasn't more prominent in WoW), and having that added utility of several different Auras was kind of cool when your group needed a specific one.
Maybe I'm just seeing issues where there aren't any, but when I logged into my Paladin the other day -- a character whom I was considering playing again for Mists of Pandaria -- I was just struck with the overwhelming sense that "This is not the character that I created eight years ago".