I've noticed that a lot of modern, indie, narrativist games grant resources to characters when they fail, which can be used at a later time to make success more likely. This relates to the standard Hero's Journey/Emperor Of Everything storyline, where the hero gets his butt kicked mid-story in order to come back and win in the end. 

So try this: every time a player fails a roll, for anything, give him a token. Let them spend tokens later for a one-time bonus to any roll later. 

This means every failure comes with a consolation prize and some interesting future choices for the player to make. This is particularly important in that it defuses some the frustration felt when a perfectly good plan is spoiled by cruddy die rolls.