Paladins are Defender with a minor in leader, just like Fighter are somewhat strikers and swordmage somewhat controllers. Their overall usefulness depends on the party make up but they are by no means failures. Even with the available powers at this point, they are a solid team member. A CHA paladin is also a pretty good social character.
As for stickiness, it is overrated. Sometime, the fighter is too sticky for his own good. The other classes need to take some hits too. A wizard that ends his day with 6 healing surge has essentially wasted a chunk of the party's ressource. In that sense, the Paladin's ability to lock down the toughest foe on the field is usually sufficient. You just have to get the squishier PC to man up a bit and realize they aren't that squishy.