Unable to create a relationship with save method of Neo4jRepository

Spot on. We moved towards more usage of elementId() in the SDN 7.1 release. Those change should have happened more transparent than it actually was.
Good news: it has already been fixed in Relationships not stored/deleted on update of node (Release >=7.1.0) · Issue #2728 · spring-projects/spring-data-neo4j · GitHub

Some background:
The CypherDSL uses a 4.4 (Neo4j LTS version) dialect as default. There is no "stable" elementId() available, so it falls back to toString(id(node/relationship)). This creates a condition that can never be fulfilled.
This is actually not a bug because CypherDSL has been told to talk 4.4.-syntax but you connect to a version 5 instance that happily returns elementIds from the nodes and relationship via the driver. So the unified id type is the elementId-String. And given the huge test base in SDN, we did not see this coming. Why? Because we configured the CypherDSL to use the NEO4J_5 dialect.
You can / should also do this by defining a CypherDSL configuration bean:

@Bean
Configuration cypherDslConfiguration() {
	return Configuration.newConfig().withDialect(Dialect.NEO4J_5).build();
}

Where I miserably failed was on mentioning this anywhere in the documentation of Spring Data Neo4j.
Even though we are getting more lenient with the bug fix regarding the given default dialect configuration, you should consider defining the dialect in your database.