First, let me get a few things out of the way: 1) Skill points are bad and they shouldn't come back. 2) Lookup-tables should never be used for uncommon occurrences when a simple linear rule will do. (Both of these points are based on time and effort vs. enjoyment; I hope I never spend 2 hours allocating skill points for a 10th level character, only to never roll 90% of them at any climactic point ever throughout the campaign, or have an exciting moment bog down as we do a roll-call lookup of everyone's strength.)
That said, I like the _idea_ of doing something more interesting with skills, just like I love the _idea_ now of feats (and also skill powers and knacks) that let you longjump w/o a running start, or never roll less than 7 on athletics and acrobatics, or calm down animals. I still end up taking skill-focus instead (or, let's be honest, a non-skill feat), but I love the _idea_.
4e did a lot right with letting you forget what wasn't important to your character. Dwarves AC bonus vs. giants, for example, was left out because it was a detail that usually didn't matter, cluttered up the races list of benefits, and was often forgotten. So, gone. But if it's important to YOUR character, hey, take a feat.
I think skills are the same way. The base rules should be SUPER SIMPLE for each skill, but for the skills that are important to YOUR character, you should have a way to make them be awesome. I guess you could rip out the "choose skills" step of character creation and replace it entirely with stuff like that. But I have a feeling that the easiest way to do this is better and more feats, skill powers, knacks and themes: more, and better, of what's already there.
Just please, PLEASE, keep the _base_ system super-simple (no skill points, no lookup tables), so the 90% of characters that aren't climbing-monkeys can get by easily while the other 10% get their moment in the spotlight.