Actually, I think the AD&D method worked pretty well. It was maybe a shade too restrictive, but giving each class its own non-proficiency penalty makes sense. It could easily be adapated as follows:
The standard classes have a non-proficiency penalty as follows:
Wizard (as commoner): -4 to hit, start with 2 simple weapons
Thief (as expert): -3 to hit, start with 3 simple and 1 martial
Cleric (as warrior): -2 to hit, start with 3 simple, 1 (blunt) martial, and deity's weapon
Fighter: -1 to hit, start with all simple and 3 martial
The penalty represents a class' level of general training. A fighter can adjust the lessons learned for one weapon to other, similar weapons on the fly. A wizard or commoner does not have enough experience or training to do so--the best they can do is learn the moves associated with a given weapon by rote, and they are relatively helpless with another.
For an extra layer of complexity, impose an additional -2 penaty if there is no similarity between the weapon used and any of the character's proficiencies.
I don't advocate granting new proficiencies AD&D style, though. Buying more with skill points would make sense in 3e, but skill points might not exist in 4th ed. Since additional weapon proficiencies don't significantly increase a character's power, however, perhaps it could be handled in-game through finding a trainer or simply practicing with a weapon for X combats.
I do like the idea of spreading the acquisition of proficiencies out so that dipping into a martial class doesn't grant a slew of new weapons all at once.