In my local D&D group I've been discussing the skill check mechanism for 3.5. In my opinion it makes no sense or at best little sense to have a d20 as a die roll. First of all its a flat distribution. Secondly ability bonuses add between 1 and 4. Yet to get a +4 you need an 18. That's quite an uncommon value and you only get +4? So randomness is more significant that character abilities! More so, training is way more valuable than abilities. What ever happened to the saying "Quos naturat non dat Salamanca non praestat". As if any fool could become a master craftsman if he works at it long enough.
As an alternative I've seen 2d10 as die roll suggested and here's some math I see that backs it up. Let us take a look at the following graph (rendered with http://anydice.com/):
This shows the percentage chance of rolling at least the value on the x axis. The black line is our well known 1d20 (with its classic 5% steps). The orange line is the curve for 2d10 (notice it starts at 2). The blue line is the normal 3d6 ability roll and the green is the more commonly used 4d6 drop the lowest ability roll.
Lets set up a simple rule that says a skill check is done against the skill's ability and the player needs to roll lower than the associated ability to succeed. Clearly the 2d10 is a tougher roll for characters with a low value. Rolling a 6 or higher happens 75% of the time with a d20 and nearly 90% of the time with 2d10. But that's all right if you're dumb your dumb. Now as you reach 11 and 12 the orange line goes below the black line and it is harder to roll 15 or higher (mess it up) with the 2d10 than with the d20. Which is also reasonable. If you're smart you're smart and things begin to get easier.
Now for DCs and training. Instead of having absurdly high values like DC 20 or what not just have 0 for trivial up to 5 for very hard. If you add 5 to the 2d10 die roll (equivalent to moving the green line 5 to the left) you see that a character with a 15 ability has a 65% chance of blowing it. Which is pretty high for an gifted character. One with 18 would have a 35% chance of blowing. Your average human with an 11 would blow it 85% of the time.
Training could then go from 0 for basic training to 5 for grand master or some other title you come up with. A grand master with an ability score of 11 would still succeed 85% of the time. Showing that mastery in the field counts. On the other hand an expert with a simple +2, but a 15 ability, would succeed 90% of the time. A worth while benefit for being gifted by the gods.