In my opinion, a cryptocurrency with real backing may work. However, at the risk of being redundant, it does have to be real backing. I have to be able to really trade my currency for the real backing at any time. Including in a "run" situation, because ironically the inability to weather a run on the currency radically increases the likelihood of a run. It can't just be an "in words" backing, where everyone politely agrees that there is a fictional backing, because in a significantly-sized economy, somebody will figure out how to exploit the difference between the real and perceived backing... which manifests as bringing the real and perceived backing into forcible equilibrium.

There's at least two major problems with your particular proposed backing: Computation power isn't actually worth that much, and the value of a given amount of computation power is sinking fast, and will continue to do so for the forseeable future. This creates practical problems in providing enough backing to power an economy. And a couple of "bonus problems": Allowing people to perform arbitrary computations on your hardware can have certain legal problems, and the process of solving this problem may raise nontrivial overhead. Backing your currency with a service rather than a good has interesting implications in a "run" situation because you've added an unavoidable temporal component to the process of cashing out the currency, which is the sort of thing you could probably squeeze a PhD thesis out of describing the precise effects of that, but I doubt they're very good. But at least it would provide a non-zero backstop to the currency, which would be a start.

(Interestingly, if we ever hit a final equilibrium on the price of computational power, note my two major objections go away. While some practical problems remain, one could imagine the rest could be worked out. Could a computation-backed BitCoin variant be what powers Economy 2.0 in Stross' Accelerando?)