I recently rerolled alliance with some RL friends about 4 months back and have a 70 mage, 65 priest, and a 18 druid and you could come hang with us.
!!!HOWEVER!!!
Their server is a PVE server, so you wouldn't be able to go back to the awesomeness of ganking.
As for the (finally) announced paladin changes!!!
My main character is (was ;_ a holy arena paladin that gradually saw less and less action as the seasons went on. The changes aren't really what I was hoping for, but they are a lot more creative than what I wanted anyways.
I think there are enough new tools added to arena healing to at least be optimistic until there is more information. I was actually really disappointed until I saw that a holy shock crit makes your next holy light spell be instant cast. *That* is frickin sweet. Even in all PVP gear (no access to BT or sunwell), My holy light crits were around 65% of someone's health in one cast.
When I first got my newish mage to 70 and started doing arena, I was pretty overwhelmed by all the things you had to do coming from a paladin. Giving paladins more tools is awesome, and being a mix of proactive and reactive is excellent. I still was hoping for a flash of light style spell that was less mana efficient, but could be casted while moving, but I think the new stuff is great.