Can the error log, and the dse.ldif(master and replica) please be provided?

Sorry I do not have it, but you can easily replicate everything you need with tehse steps:

1. Install IPA master on server1
2. Install IPA replica on server2
   (make sure the 2 start replicating to each other using GSSAPI auth)
3. Uninstall IPA server2
4. Immediately reinstall IPA replica on server2 (keep the same server name)
   At this point you will see that master server1 is not able to properly authenticate against the replica because it has the old ticket in the cache.

Ticket has been cloned to Bugzilla: https://bugzilla.redhat.com/show_bug.cgi?id=830338

I was finally able to reproduce the problem, here are the exact steps:

[1] yum install ipa-server bind-dyndb-ldap on two systems A & B
[2] on A: ipa-server-install --setup-dns (use Secret123 for passwords, and EXAMPLE.COM for realm)
[3] on A: ipa-replica-prepare <host name for B> --ip-address <IP address of host B>
[4] on A: kinit admin
[5] on A: scp /var/lib/ipa/replica-info-<hostname of B>.gpg root@<host B>:/var/lib/ipa
[6] on B: ipa-replica-install --setup-dns --no-forwarders /var/lib/ipa/replica-info-<hostname of B>.gpg
[7] on A: add a test entry:

ldapmodify -D "cn=directory manager" -w Secret123 -a
dn: cn=mytest,dc=example,dc=com
objectclass: top
objectclass: groupofnames
objectclass: groupOfUniqueNames
cn: mytest

[8] on B: search for the new entry to verify replication is working

ldapsearch -D "cn=directory manager" -w Secret123 -b "dc=example,dc=com" -xLLL cn=mytest

[9] on A: ipa-replica-manage del <hostname of B>
[10] on B: service stop sssd
[11] on B: ipa-server-install --uninstall -U
[12] on A: ipa-replica-prepare <host name for B> --ip-address <IP address of host B>
[13] on A: scp /var/lib/ipa/replica-info-<hostname of B>.gpg root@<host B>:/var/lib/ipa
[14] on B: ipa-replica-install --setup-dns --no-forwarders /var/lib/ipa/replica-info-<hostname of B>.gpg
[15] on A: check the error log for GSSAPI authentication errors:

/var/log/dirsrv/slapd-EXAMPLE-COM/errors:

[21/Jun/2012:13:11:44 -0400] slapi_ldap_bind - Error: could not perform interactive bind for id [] mech [GSSAPI]: error 49 (Invalid credentials)
[21/Jun/2012:13:11:49 -0400] slapd_ldap_sasl_interactive_bind - Error: could not perform interactive bind for id [] mech [GSSAPI]: LDAP error 49 (Invalid credentials) (SASL(-13): authentication failure: GSSAPI Failure: gss_accept_sec_context) errno 0 (Success)

Mark, excellent writeup,
just for testing you would get a faster setup if you avoid --setup-dns (just make sure boht hosts have appropriate entries for both in /etc/hosts) and also usinf --selfsign so you can skip the whole slow dogtag install).
Neither DNS nor dogtag are required to reproduce/verify this bug

Thanks, and thanks for the tip!

I have a fix that I will be sending out for review soon. There is an initial failure, but then the authentication succeeds, and replication is successful:

[27/Jun/2012:10:07:08 -0400] slapd_ldap_sasl_interactive_bind - Error: could not perform interactive bind for id [] mech [GSSAPI]: LDAP error 49 (Invalid credentials) (SASL(-13): authentication failure: GSSAPI Failure: gss_accept_sec_context) errno 0 (Success)
[27/Jun/2012:10:07:08 -0400] slapi_ldap_bind - Error: could not perform interactive bind for id [] mech [GSSAPI]: error 49 (Invalid credentials)
[27/Jun/2012:10:07:08 -0400] NSMMReplicationPlugin - agmt="cn=meToibm-ls22-04.rhts.eng.brq.redhat.com" (ibm-ls22-04:389): Replication bind with GSSAPI auth failed: LDAP error 49 (Invalid credentials) (SASL(-13): authentication failure: GSSAPI Failure: gss_accept_sec_context)
[27/Jun/2012:10:07:14 -0400] NSMMReplicationPlugin - agmt="cn=meToibm-ls22-04.rhts.eng.brq.redhat.com" (ibm-ls22-04:389): Replication bind with GSSAPI auth resumed

The last line if the important one:

[27/Jun/2012:10:07:14 -0400] NSMMReplicationPlugin - agmt="cn=meToibm-ls22-04.rhts.eng.brq.redhat.com" (ibm-ls22-04:389): Replication bind with GSSAPI auth resumed

attachment
0001-Ticket-366-Change-DS-to-purge-ticket-from-krb-cache-.patch

[mareynol@localhost servers]$ git merge ticket366
Updating b2a9269..14cb1d0
Fast-forward
ldap/servers/plugins/replication/replutil.c | 2 +-
ldap/servers/slapd/ldaputil.c | 47 +++++++++++++++++++++++++++
2 files changed, 48 insertions(+), 1 deletions(-)

[mareynol@localhost servers]$ git push origin master
Counting objects: 17, done.
Delta compression using up to 4 threads.
Compressing objects: 100% (9/9), done.
Writing objects: 100% (9/9), 1.60 KiB, done.
Total 9 (delta 7), reused 0 (delta 0)
To ssh://git.fedorahosted.org/git/389/ds.git
b2a9269..14cb1d0 master -> master

Added initial screened field value.

389-ds-base is moving from Pagure to Github. This means that new issues and pull requests
will be accepted only in 389-ds-base's github repository.

This issue has been cloned to Github and is available here:
- https://github.com/389ds/389-ds-base/issues/366

If you want to receive further updates on the issue, please navigate to the github issue
and click on subscribe button.

Thank you for understanding. We apologize for all inconvenience.