> What are the main challenges that explain why it hasn't been completed yet?

Because its pretty hard to define even what "decentralized currency exchange" means, and, particularly, to identify a mechanism by which you could do order matching in such a system so that wouldn't leave you with just a bunch of disconnected exchanges that are far less efficient at market clearing than a centralized exchange.

buttercoin literally just started 2 days ago (on 4/13). It's coming along quickly, a lot of developers have shown interest. It might be a while before we see an exchange based on this project. There are other high performance exchange projects starting up too.

I don't think buttercoin vs any of the existing exchanges has any proper analogy that would match your git/mercurial vs svn example. The only diff between buttercoin and those is that it will be open source. It doesn't actually decentralize. You might even see MtGox take buttercoin and use that to run their exchange.