Binary success-failure is boring and somewhat out of tune with reality. But combat has multiple rounds, so as long as you're running the fight at a good pace, it's totally fine for some rounds to be 'failures.'
Contrast that with, say, Persuasion. By the default way of doing things, you say, "Help me, oh wise NPC," then make a Persuasion check. Maybe your modifier is great, but you screw up. Oh well, that's a failure.
But what if you use an alternate system, slightly akin to the much-maligned skill challenges of 4e? Make it work more like combat. Say that there are 5 steps of the negotiation -- figure out his personality (Insight), form a rapport (Persuasion), figure out what he wants out of the situation (Intelligence), make an offer (Persuasion), and close the deal (Persuasion). Perhaps swap one of those persuasions with Deception if you're trying to trick him, or Intimidate if you want to scare him.
At the end, how much you get depends on how well you rolled. Maybe you didn't form a great bond (failed Insight), but he trusts you (successful Persuasion) and you at least understood his interests (Intelligence success). Your initial offer kinda sucked (Persuasion failed), but you bit the bullet and agreed to a deal he'd accept (successful Persuasion). Three success out of five attempts is enough to get some aid, but not everything.
Make skills less binary. Make it work more like combat, with give and take. And, of course, narrative each step of the way, both in battle and in diplomacy. I think it's a good system.