If they make the new melee paladin anything but strength it'll completely ruin the paladin for me. They've always been the holy warrior schtick to me. Not the the guy who wails on you with a sword using his mighty wisdom or personality.
I've always had trouble conceptualizing any stats other than strength or dexterity for a weapon attack. A magic attack of some kind, sure. I just can't see a weapon attack.
In that case Avengers, Swordmages, Battleminds, Ardents, Bards, Druids, and Artificers should all switch to Strength because they all have melee powers.
4e is full of abstractions in the name of variety and balance. It keeps things interesting. And a bit of imagination goes a long way in explaining away training. An artificer's sword may be driven by his cunning, his experience, and his analytical assessment of an opponent, while a dwarf avenger may be observing his opponent, using his insight to predict their movements, and strike just at the right time with precision. These are heroes, they can have 10 strength on a piece of paper, but really they are well trained, proficient and strong enough to wield their weapons. There is more to using a weapon than brute strength or agility. As many duels have been decided by sheer luck as those determined by the strength or experience of the duelists.
I look at it this way, a level 30 fighter can beat up a level 1 fighter with his bare fists, wearing no armor. So an Avenger is using his Wisdom like the high level fighter is using his levels, to give him an edge. It's an abstract system. What's most important is relative equality among same level PC's. If there are some melee classes that use strength as a primary stat, and others that don't, equality becomes hard to establish when basic attacks are based only on strength.