It seems like the only GOOD paladin comp is Pal/Mage/Spriest. People say paladins are soooo OP, but wheres the representation? The next best thing is like TSG. Pal/Mage/War or Pal/Lock/War just can't do anything vs. Lock/Shaman teams. Yes, Paladins worked GREAT for the first couple weeks before people had the resil to survive more than 1 min, but now... they're just falling behind.
Too bad mage spriest is atleast twice better with a resto druid.. Well what can you do, better to ride the carry-train from these two nice fellows before its nerfed.
Shadowcleave with paladin feels to have slightly the same issue as mage+spriest, its probably better with resto druid instead. Only difference between shadowcleavedruid and shadowcleavepaladin is probably that meleecleaves wont zerg your paladin in first 30seconds, they will just wait till you pop bubble.