Non-Combat encounters should be fun, not frustrating!
I'm a veteran (AD&D) DM running D&D 4e, and my first-time players really enjoy the game I'm running for them. Though, the skill-challenge mechanic is frustrating for all of us - DM and player alike.
Specifically, the pure pass-fail mechanic is demoralizing (even though combat doesn't seem to feel that way to them.) A player thinks up a clever way to overcome a portion of the challenge as-written, I give a +2 for cleverness, the party helps for another +2 and BAM, a bad role or untrained skill means it didn't work.
I know this is an old complaint, and entire RPGs have been designed around this very problem. But I don't want to play another system, I just want skill challenges to feel a little more "yes-and" or "yes-but".
What existing systems have you seen (and played) that are successfully adapted for play with D&D 4e? A big bonus to any system that doesn't penalize player agency heavily just because the appropriate character-skill is untrained...
Please: Don't just name a system and call it "better", describe it and explain how it fits with D&D 4e.
Clarification: The frustration isn't with the entire challenge being failed, that seems to never happen - the problem is with the pass-fail nature of each individual skill roll... For counter-example, I've heard of systems that have trinary logic: Pass/Pass-with-complication/Pass-with-benefits...