Hi Ben,
40 min sounds far too slow. Better should be 40 ms. :-)
Can you tell a little bit more details, f.e. how many nodes and rels do you have, how do you use Neo4j (embedded Java, REST, language binding), or anything else what might help to figure out what goes wrong (data model, queries, use cases)?
Greetings
Axel