I have never worked with graph databases such as neo4j, I would like to know if they support easily replication and clustered distribution as well as key-values databases, or if there inherent structure makes it really difficult/ slow
Graph databases are hard to distribute, especially if the database wasn't designed upfront as a distributed graph database.
Titan is a distributed, real-time, transactional graph database that was designed from the start to be distributed. Titan can use either Cassandra or HBase as its distributed data store, and it's capable of supporting tens of thousands of concurrent users interacting with a single massive-scale graph represented over a cluster of machines.
Titan is Apache 2.0 licensed, and it's the first native Blueprints implementation so it integrates with the entire TinkerPop stack, which is BSD.
even that the way to distribute data in graph databases is not that easy as in key-value stores, where the keys are distributed by ranges, there are techniques to distribute a graph.
InfiniteGraph (made by Objectivity) for instance is a highly distributed graph database. It uses a P2P technology to increase read and write performance by growing the hardware. It allows the user to cluster a certain part of the graph or a certain kind of information as its needed and to distribute it over some machines as its needed too.
As I heard this process of clustering/distribution will be eased for the user in release 3.0. A parallel query mechanism is also planned, that allows to run one query concurrently on the machines.