I think the one point that prevents anything from being truly decentralized is finding peers--at some point you have to know (and trust?) at least one other peer.

I believe the current way that the bitcoin client finds its first peer is:
  1. IP addresses of well known nodes
  2. DNS seeding

It's possible that all of these IP addresses are offline and/or DNS address(es) stale; or worse: maliciously changed, so that you cannot get your first (good) peer.

Forgive me if this information is no longer correct, I am a noob.