I tend to disagree that paladins were bad. It was just hard to play them as a third option. Everyone was so obsessed with Warrior and Mage playstyle, that he failed to see how a mix of them could do well. Here's an example of how to play a weird Paladin in KBAP/KBCW:
I do find the Skald to be a bit overpowered. I suppose the warrior took a leadership nerf cause some of the new skills would make him a beast of he had too big of an army. Still, as far as buffs go, the difference between lvl 1 Stoneskin and lvl 3 stoneskin is big, and the Warrior won't be able to see much from it until late game. Having healing as a set spell is just plain awesome - it makes the skald a prime target for a no-loss play, especially if you can get some higher HP units quickly.
We will see how this KB plays out. It may just turn out to have made all the 3 classes interesting.