Just wanted to pop in and mention that I've been working on an almost identical concept for about 3 years now, although it's only been tied to crypto for about a year or so. I started working on this concept back when I started grub.org in 1999. I haven't had time to digest all the conversations here, but I will post back once I've read them and hopefully have some useful comments to add to the conversation.
It is inevitable the blockchain will be tied IT infrastructure. The majority of the world's CIOs basically spend their days worrying about trust. With the blockchain, you get computed trust. Better even if you can apply that computed trust to more compute. It seems logical you could expect every major corporation on the planet to get involved in this over the next 5 years. If you come from an IT background, you'll realize these companies will want to 'own' the code that sells their equipment. For a taste of that behavior, just take a gander at the OpenStack community.
One point that I'd like to make now is that the proof-of-work (which I call 'proof-of-virtualization') for this type of service is a bit difficult to pin down. Proving you run capacity to virtualize something is going to be tough without running some type of mining workload. Proving you virtualized something for someone is a bit easier if you can sign transactions. One possible way to do this is through KVM's guest-to-host serial port call.
Proving you ran a workload without making a copy of it or the payload data is, from what my advisors and I can tell, nearly impossible. This means trust for some high trust workloads will have to still run through human trust channels, similar to how they are done today.
It is this last point that I'm focusing my business on: providing a high trust service for establishing identity and capacity of compute resources. This is, for good or bad, not necessarily a job for a cryptocoin. That's not to say a cryptocoin isn't useful for providing trust at a separate layer. Knowing you just got paid before spinning up an instance is a wonderful thing: the amount of fraudulent payments in the IaaS industry is ~10%. This fixes that handily, in addition to a whole host of other issues that have very little to do with a new coin.
If you'd like more information on the project, the Github repos (code always first!) are here:
https://www.github.com/stackmonkey/, and the pool (where you can start an anonymous instance) is here:
https://www.stackmonkey.com/I'll be back.