While I've been pointing out the problems I've encountered with Neo4J and OrientDB, I should say as a counterpoint that I just tried Blazegraph based on this recommendation, and so far, it works.

Its importer was not the most intuitive thing to use -- I had to dig up configuration items that were scattered across its documentation and Stack Overflow -- but I got it to work, it imported 25 million edges in less than 8 minutes, and it's providing reasonably quick access to those edges now.