People need to be more careful when using the term "backing" when referring to money. It has a very specific meaning but is usually perverted and causes lots of confusion.
"Backing" means that a party guarantees to exchange one asset for another upon redemption at a fixed rate. In the case of gold-backed USD, the banks guaranteed to give you gold in redemption for the paper, and this was at a fixed rate. Thus, the dollar was "backed" by gold. That's what backing means - a counterparty specifically promising to exchange one for the other at a certain rate.
Thus, Bitcoin is not backed by anything. Nor is gold backed by anything. Nor are dollars today backed by anything.
It is wrong to say that Bitcoin is "backed" by electricity, or cryptography, or the size of the Bitcoin economy. It is similarly wrong to say the USD is backed by the government, or by violence, etc. To do so is to pervert the term. Bitcoin is not backed by anything, and that is just fine, because it's a commodity unto itself and is valuable for its specific attributes. It needs no "backing" - it is a thing unto itself which we value. Same for gold.
If you find yourself in the position of saying Bitcoin is backed by something, change the term to say "Bitcoin is valuable because..." Or, "the USD is valuable because..." The answer to those sentences will be valid, and you won't be caught in the misnomer of "backing."
IMO, even with your more precise definition of "backing", Bitcoin is still backed by "(statistical) proof of work" and a public transaction record. If all of the miners decide to stop offering this "proof of work" or "puiblic transaction record" when it becomes time to redeem your coins: they are worthless. This worthlessness would be despite the past "proof of work" and "public transaction record" used to generate those coins. The advantage Bitcoin has over fiat in this case, is that a group of people can get together and start building the block-chain again; in the unlikely event that the network shuts down for an extended period of time.
Sorry, for the run-on sentances
No, I think evoorhees was right. Bitcoin is backed by "(statistical) proof of work." It has PoW, but that isn't worth something of value. I'm not going to go someone and trade my bitcoins for a double sha256...