How about that Penalty at -10 for an "untrained skill"?
We could boost it up to -20 instead, so that raising skills becomes more interesting and less based on your core stats.
Using a skill in the current system allows you a lot of flexibility- in terms of picking a stat which are you superior are. The idea to be able to use any characteristic is very good, but with the relatively higher starting stats on characters, this make skill rank raising relatively unattractive at low ranks and even mid-ranks, until such time where the DM decides to start boosting up the difficulty of them challenges.
A -20 would still give people a 25-35 chance of success, instead of the 35-45 (assuming people favor buying a few extremely cheap stat advances at the beginning) that most people would have gotten with just a -10.