Problems with creating Open Directory Replica on OS X Server 5.1
Note that although I got the same error, I am on macOS 10.12.6 and Server 5.3.1.

I documented what I did, step-by-step.  I'm not exactly sure which of these steps made the difference but my hope is that this will help someone.

In my case I have a server on the west-coast and another on the east-coast using a site-to-site VPN and two different /24 IP subnets, so communication can happen but replication obviously failed.  Before starting I recommend having the same macOS version/build numbers as well as the same server.app version.


Blow away OD on both sides.  I used $ sudo slapconfig -destroyldapserver.  Make sure to have a backup of your data first.
Get DNS working perfectly.  This involved going through Server.app's "edit hostname" process and (in my case) using a FQDN.  When you change the hostname and you're asked to select whether the server is operating on LAN-only, LAN + VPN, or Internet, select either the LAN + VPN or Internet options.  This is so that the server creates DNS zones that aren't ".local", which I think is one of the core issues that prevented replication working, because .local is for Bonjour and I think that messes things up.

So I changed the computer name to "Company X Vancouver Server" and the hostname to vanserv.clientcompany.com.  Restarted the server, checked things out with $ changeip -checkhostname and verified forwards and backwards DNS are working with the "host" tool, looking up both the IP and the hostname, and making sure it resolved both ways.  Set the server to use 127.0.0.1 for DNS first, then its other IP (192.168.10.10), then local next-hop router, then public DNS.  Restart.

I did exactly the same thing on the east-coast server, calling it "Company X Toronto Server", and hostname "torserv.clientcompany.com".

I made sure there were entries on both servers for the other server.  So vanserv has vanserv.clientcompany.com (192.168.10.10) and torserv.clientcompany.com (192.168.20.10).  Checked forward- and reverse- DNS lookups for the other server on both.  And pinging torserv from vanserv would resolve and return packets, and vice-versa.

I set both servers to "perform lookups for only some clients" - and I set that to the server itself, only.  This is so that DNS lookups for the company's domain, clientcompany.com, don't go to the server and fail to resolve, such as a staff member at the office visiting the company's website.
Create the primary OD, but leave it empty.  Restart.  Join the replica to it using the FQDN - in this case the OD was created on vanserv and I joined torserv to it as a replica.  I used the FQDN vanserv.clientcompany.com instead of the IP address.  Success!
Populate the OD with data, make sure it replicates successfully.  It did!
Add in locales (optional) - I defined 192.168.20.0 as Toronto and set that server to torserv.clientcompany.com, and Vancouver as 192.168.10.0/24 and set that server to vanserv.clientcompany.com.


So my suspicion is that the "network problem" as well as the "different version of macOS" errors I was getting in the server.app GUI really were just a lack of good communication happening due to DNS being configured in a way that server.app didn't like.