PVE: The class works quite good and the new spells which we have gotten along with holy power has made it a lot more fun than wrath 1 button spamming. A paladin isn't hard to play decent, however, it is hard to play it good and by this I mean using AM where it will benefit the most circulating your CDs (I love being able to push out significant more healing on demand) in order to "meet" incomming damage.
We got Hand of Sacrificie which is brilliant, Divine Protection, Divine Shield, Hand of Salvation, Hand of Freedom which all when used correctly is amazing tools.
And we got an "oh shit" button - Lay on Hands.
Paladins in PVE is one of the strongest healers and offers quite a big arsenal of abilites, however, since the recent patches the "gap" between the classes isn't that big anymore - Except for druids, utterly useless class "hello, my healing will be there in a few seconds - Oh damn, I'll just CR you then".
For PVP - I don't know and don't really care.