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?)
So, how about if someone would get a farm of computers mining bitcoins, at a rate where the bitcoins pay for the electricity etc, but then they also rent out this computing power for anyone to use for whatever purpose (like Amazon), but for this accept payment only in bitcoins, being the exact amount of bitcoin that would have been mined otherwise with the computing power rented out.
Would that work?
Then you back it with something else of value, namely computing power, but you only accept bitcoin as payment.
Just a thought, though.