Do you really need a new cryptocurrency for this? I thought about how to build StorJ many times and at no point did I never need anything more than standard Bitcoin as it exists today.
Using a new cryptocurrency to bootstrap it. It pretty much is standard Bitcoin just with just some extra data in the transaction, like Datacoin. We can store basic metadata about where the files are and their status.
This allows us to launch something now, and then we can get a little more creative, and remove our dependency on a blockchain. I've read gmaxwell's and jgarzik's writings over and over again. Love to hear your ideas.