Shoot. I should have replied to this thread.
After spending a bunch of time with Apple Support, I figured out that there's a computer group called com.apple.opendirectory.group that is retaining records of previously connected replicas, and this data isn't being removied or over-written.
So, here's what you do:
On the Master remove the failed replicas from command line
$ sudo slapconfig -removereplica replica.fqdn.priv
$ sudo slapconfig -removereplica replica2.fqdn.priv
On both replicas, run this command
$ sudo slapconfig -destroyldapserver
On the master open /System/Library/CoreServices/Directory Utility.app
Click on the "Directory Editor" tab
Change the node to /LDAPv3/127.0.0.1
Go to ComputerGroups
Select the com.apple.opendirectory.group
Delete the offending replicas from GroupMembers (you'll have to figure out the replica's GeneratedUID, which I do by looking at the computer accounts), GroupMembership and Member
Now you should be able to re-connect the replica
That explains a few things then as i was importing computer groups originally. I have since today however abandoned all hope of complete replication however and reverted to each site having a standalone server. Reason being, once i had gotten a server replicated the one time replication worked fine, however subsequent ones did not and the LDAP log consistenly gets full of ldap_sasl_interactive_bind_s failed errors on both the master and replica.
Unless you have any insight on this also, i'm unfortunately stuck with multiple masters at each customer site (which is a real pain for management).
Thanks for your response however, that did at least explain how I got 1 server connected this morning (as i'd actually demoted that one when in 10.6 prior to the 10.7 install.
I tried your suggestion and I am down to this error. Any feedback on how to fix this. The OD Master is brand new installed.
sso_util command failed with status 2
2012-09-22 11:58:53 +0000 _preflightLDAPReplica: could not read the Kerberos realm from the master server.mydomain.com
2012-09-22 11:58:53 +0000 Not creating replica due to failure to read Kerberos realm from master. (error = 78)
2012-09-22 11:58:53 +0000 Not creating replica due to preflight failure.
2012-09-22 11:58:53 +0000 Not creating replica due to preflight failure. (error = 78)
Thanks in advance for any feedback.