Eventualy, the problem was the definition of my neo4JRestGraphDatabase (which unfortunately I haven't pasted here...).
It was:
<bean id="graphDatabaseService" class="org.springframework.data.neo4j.rest.RestGraphDatabase">
<constructor-arg value="http://localhost:7474/db/data/" />
</bean>
Instead of:
<bean id="graphDatabaseService" class="org.springframework.data.neo4j.rest.SpringRestGraphDatabase">
<constructor-arg value="http://localhost:7474/db/data/" />
</bean>
Now I have 'Connection Refused' problem, but this is another issue.
Regarding the dependencies, the dependencies that geceo mentioned above are indeed enough.
Thanks for anyone that tried to help!
Carmel