3e Paladins...get +CHA to all saves. It's like a better version of the Hexblade's Arcane Resistance, really. (But then again, Hexblade+Blackguard = lol saves). That aside, they're...not much better than fighters, frankly. Who in turn are not very good without PrCs.
...welcome to 3e melee.
4e Paladins...well, CHA isn't the main attack stat. It dovetails as Cranbud states, with CHA or STR being the primary stat depending on your build (and only STR/CHA races can manage a Balanced build easily enough). CON's importance is...a few things for Paladins.
1: Earlygame HP. The spread is still quite narrow, though nowhere near as bad as 3e.
2: Healing Surges. They get an assload to start with. They typically need that assload. That aside, they do have powers that burn Surges for extra offense, should they go that route.
3: Axe/Hammer specialization feats. These tend to be the big weapons one goes for, and as a result, CON is important here, doubly as a HP/surge booster, and for direct access (Hammer more than Axe).
Other classes like extra CON for reasons 1 and 2, but also for armor availability--to be precise, armor heavier than Leather requires 13 STR and CON for proficiency, and don't even look at Plate without either autoprof or 15 in both stats--and you typically want the heaviest you can get without getting in the way of class features; the extra AC matters a decent bit.
...no, armor doesn't get in the way of casting classes' abilities for once. So if you can manage the stat distribution, go ahead and get a suit of full plate for your Infernal Warlock. You won't regret it.
