Query languages are the foundations of database teaching and education practices. The broad adoption of graph databases contrasts with the limited research into how they are taught. Contrary to relational databases, graph databases allow navigational queries with higher expressivity and lack an a priori schema. In this article, we design a multi-step exploratory user study investigating these peculiarities and how they impact the student's learning process. Focusing on the widely used Cypher graph query language, we studied a new taxonomy for classifying the errors around graph queries and conducted an in-depth analysis. Our investigation highlights several learning barriers, including misunderstanding the semantics of language constructs, the confusion between data and schema, and the pattern-matching mechanism. We expect the lessons learned and the derived best teaching practices to have an impact on database education and to influence future generations of students, researchers, and practitioners working on graph database technologies.