DnD Skill Challenges

Skill Challenges are a new wrinkle in DnD skill use that aim to make said skills use… well, more interesting. The basic idea is that each Skill Challenge has a Complexity rating from one to five.
A Complexity One skill challenge for a group of level 1 adventurers, for example, requires that the group as a whole succeeds at 3 skill checks before it fails at 3. A complexity Five skill challenge is something like “succeed at 11 before you fail at 7”.* The idea is that everyone around the table who is involved is taking turns at working on this challenge, either by making their own skill rolls or helping someone else hit theirs, and that each of these ‘moves’ is roleplayed/narrated as you go, making the whole thing more interactive.
In an ideal world, there are a few ‘obvious’ skills that work for each encounter, and the unspoken challenge to the players to come up with novel ways to apply the skills they’re good at that aren’t on that pre-approved list. It’s all very, if I may say so, hippy and indie. It’s a LOT like how all the skills and combat in Heroquest work.
In practice, the Challenges have come under a lot of fire, both because the Difficulties for success are weighted HEAVILY toward failure in some places, and because people are having trouble getting their heads around it, and finally because the results of the Challenge are, as written, binary: you either Win Completely or fail completely.
Enter Keith Baker, and some excellent thoughts on making Skill Challenges interesting and winnable, without actually changing the math. (Which I’m doing anyway.)
One good suggestion is something straight out of Heroquest, but predicated on the DnD Combat model: more graduated levels of success, ranging from the Crit-like total victory, to a regular old Success, to Moderate success, partial success, failure with some benefit, failure with a single mote of light, and the Crit-fumble of Total Loss.
But the best suggestion is one I’ve been working on for what seems like years, now: setting up conflicts so that the failures are as interesting as the victories.
* – I know the numbers I quoted for Complexity values are off, compared to the rules — I’m quoting a mathmatical rework of the rules that makes more sense to me.