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 bonus to any roll later. Every failure becomes a chance of future success when they need it most.