Even if you get rid of the weapon soon after without really using it the value you can get from the 3 cheap recruits and a Knife Juggler hits or boost from Sword of Justice or just filling up the board is good enough for the mana cost.
Finally a way to see Paladin back up into the Light!
WOW! Extremely good card, i'm surprised that it's just rare, it might as well go as epic card. You got more than double mana value ( 7 mana worth for 3 mana), and there's a lot of combos with a lot of both paladin and neutral cards. And what is really good is that this card will work well in both control and aggro archetypes of decks. In control deck, you got some nice early board control against aggro decks (in contranst to Paladin second 3 drop, Peacekeeper, who is good vs control), and in aggro deck you got all those little fuckers to combo them in various ways you guys already mentioned.
I like this card, i think it breeds its own weenie build. I think it is problematic that it has negative interactions with TSC though, so I think you would want to forgo that for something way more aggressive, like an all in shockadin build