But that approach makes it possible to increase skills you've never used, like the "killing orcs makes you better at climbing walls" flaw of D&D. Isn't downtime training a better way to get skill increase parity, if you want it?
As to that skill-list itself, I think there are a few duplicates. For instance, Perform and Play Instrument(x). Also, recently I've come to think Fast Talk and Oratory are similar enough to be the same skill: I found myself unable to say players couldn't use Oratory in time-limited situations - so basically, it became usable as Fast Talk, and therefore unfair if the reverse couldn't also be done.
Here's my suggestions to condense the skill list:
Search = Spot [but 'INTx?' for general perception rolls, i.e. requested by the GM, not the player]
Lockpicking = (Disarm) Traps
Persuade = Fast Talk = Oratory = Seduction
Perform = Play Instrument () [and Sing/Dance are just variations]
Language () - simplify this to one skill, and a list of languages known (without individual percentages, but recently-learned ones might be at, say, x1/2).
First Aid = Healing