For the record, my choice would be
All skills are 1d20 + ability mod vs. Target Number. Target Number is determined by your level plus and DM modifiers. It starts at 17, and drops by 1 for every 2 levels (IE 16 at 2nd, 15 at 4th, 14 at 6th, etc). Being trained in a skill gives a +3 bonus. You start knowing 3 skills, and get a new skill every 4 levels (4, 8, 12, 16, 20, etc). You could break the thief skills up into the 4e skills as well, or simply remove Thievery and Stealth from the list.
It mixes old school certainty with new-school resolution.