Being able to summon a minion no matter what at turns 2 and on is amazing. How do more people not realize this?
Why does it appear to suck? Cuz the recruit never sticks around for the next turn. Now consider why it doesn't do anything next turn...because it was killed off. Which means your opponent spent some part of his turn taking care of it (i.e. A card, mana, an attack or best case an entire minion).
This is easily why the hero power needs no reworking - it makes your opponent do something they didn't plan on. And isn't it sad how many players are afraid of a 1/1 with no ability?
Now think about other hero powers - do they make your opponent react or is it your opponent using it as a reaction to one of your plays? Most likely your opponent is reacting to you through their hero power. But paladins make the opponent react to their hero power.
Imagine if your recruit does survive! Now you've got an ideal candidate to use one of many of our buffs on, or just clear one of their weaker minions out. Even better, you get to replace that honorable soldier with one of the same stats! And you can just keep doing it over and over only using an increasingly less total amount of your mana pool.
Also, people like to complain about our lack of removal...we can get them to one hp but can't finish em off. But wait! Our hero power summons a minion who does exactly that.
This is a strategy game as all card games are, and those little guys sure do make people readjust their strategy and if they don't then the recruit becomes an integral part of your army.
My knowledge and experience comes from playing ranked with only paladin (shockadin season 1-3 and midrange this season). If anything is confusing or debatable id love to hear you voice your opinion.