Regarding the earlier skill discussion, what about something like the following?
Aptitudes are broad "skill groups" that characters get only at first level. They're very similar to 4e skills, but instead represent areas of talent. Because of this, characters most likely wouldn't get very many of them (2-4?).
As someone suggested upthread, Aptitudes could be descriptive: Athletic, Deceptive, Knowledgeable, etc. Whatever the approach, they should cover a broad array of adventuring-oriented skills. A character who attempts something related to their Aptitude gains a talented bonus (like the 4e +5 trained bonus). For example, a Deceptive character would gain the talented bonus on checks such as bluff, disguise and forgery.
Characters would also receive skills. These would be fairly specific ala 3.x, such as Bluff, History, Pick Locks, and Underwater Basketweaving.
There could be four skill tiers: Untrained, Amateur, Expert, and Master. The latter three would grant automatic success when attempting checks of an appropriate DC. Maybe DC 5 for Amateurs, 10 for Experts, and 15 for Masters. Whatever the numbers, they should reflect an reasonable task for that given level of mastery. (Obviously, this should scale.)
Players would receive a certain number of skill points each level (8 at first level and 2 every level after that?), with Amateur rank costing 1 sp, Expert 2 sp, and Master 3 sp. If some skills are considered better than others, they might cost 1 extra sp for each rank, while "flavor" skills (Craft, Profession, and Performance) might cost 1 sp less. Obviously, the DM would have say as to how many free Amateur rank "flavor" skills one might acquire (or it could be capped by Intelligence).
I think the system has its advantages. Talented individuals with little to no training in a given skill would have a better than average chance of succeeding on a skill check, but no guarantees. A Knowledgeable character who's never had formal schooling would have a good chance of knowing something, but a low roll could indicate a gap in that knowledge.
On the other hand, a skilled but untalented character would automatically succeed with checks equal to his level of training, but anything beyond that might be quite difficult for him. A Master Historian has no difficulty recalling any but the most esoteric historical facts.
Finally, characters that are both skilled and talented gain the best of both worlds. A Knowledgeable Master Historian can recall all kinds of historical facts, and can often remember rare facts that are difficult for less talented historians to recall.
Discounting "flavor" skills also makes sense in my opinion. It costs a player nothing if they just want their character to be able to competently play the lute around the campfire after a long day. On the other hand, a character who's skilled enough to impress the king must pay for the advantage.
I'd also keep the 1/2 level bonus in some form. It makes sense that a grizzled 20th level veteran would be decent at all kinds of tasks. He's seen a lot in the time that it took to get to 20th level, and shouldn't be as inept as a wet-behind-the-ears 1st level journeyman. Even if he's never studied the subject himself, he's probably heard enough mages spout arcane facts that he has a chance of identifying an unknown magic. It doesn't necessarily have to be a 1/2 level bonus. It might be a 1/4 level bonus, or a 1/6 level bonus, or whatever. I do think it should be retained in some form though.