If you're using 3.3.x or above, then this should do the trick:
Rebuild the labelscanstore. To do this stop the database using bin/neo4j stop and then remove graph.db/neostore.labelscanstore.db. Restarting Neo4j, via bin/neo4j start, will rebuild these files.