"Realm not local to KDC" should be accompanied with a Kerberos client
referral telling the client which would be the right KDC to get a
suitable ticket. Can you send the output of

KRB5_TRACE=/dev/stdout ldapsearch -H ldap://example.org -Y GSSAPI ...

to see where the request fails?

Sure, here is the output:

# KRB5_TRACE=/dev/stdout ldapsearch -H ldap://dc001.example.org -Y GSSAPI -N -b dc=example,dc=org "(&(objectClass=user)(sAMAccountName=username))"
SASL/GSSAPI authentication started
[15321] 1387302064.607342: ccselect can't find appropriate cache for server principal ldap/dc001.example.org@EXAMPLE.ORG
[15321] 1387302064.607479: Retrieving host/scm.project1.example.org@PROJECT1.EXAMPLE.ORG -> krb5_ccache_conf_data/proxy_impersonator@X-CACHECONF: from FILE:/tmp/krb5cc_0 with result: -1765328243/Matching credential not found
[15321] 1387302064.607522: Getting credentials host/scm.project1.example.org@PROJECT1.EXAMPLE.ORG -> ldap/dc001.example.org@EXAMPLE.ORG using ccache FILE:/tmp/krb5cc_0
[15321] 1387302064.607644: Retrieving host/scm.project1.example.org@PROJECT1.EXAMPLE.ORG -> ldap/dc001.example.org@EXAMPLE.ORG from FILE:/tmp/krb5cc_0 with result: -1765328243/Matching credential not found
[15321] 1387302064.607874: Retrieving host/scm.project1.example.org@PROJECT1.EXAMPLE.ORG -> krbtgt/EXAMPLE.ORG@PROJECT1.EXAMPLE.ORG from FILE:/tmp/krb5cc_0 with result: 0/Success
[15321] 1387302064.607893: Found cached TGT for service realm: host/scm.project1.example.org@PROJECT1.EXAMPLE.ORG -> krbtgt/EXAMPLE.ORG@PROJECT1.EXAMPLE.ORG
[15321] 1387302064.607904: Requesting tickets for ldap/dc001.example.org@EXAMPLE.ORG, referrals on
[15321] 1387302064.607973: Generated subkey for TGS request: rc4-hmac/E967
[15321] 1387302064.607993: etypes requested in TGS request: aes256-cts, aes128-cts, des3-cbc-sha1, rc4-hmac
[15321] 1387302064.608245: Sending request (1650 bytes) to EXAMPLE.ORG
[15321] 1387302064.608565: Initiating TCP connection to stream 172.16.50.2:88
[15321] 1387302064.609355: Sending TCP request to stream 172.16.50.2:88
[15321] 1387302064.610199: Received answer from stream 172.16.50.2:88
[15321] 1387302064.610398: Response was from master KDC
[15321] 1387302064.610432: TGS request result: -1765328316/Realm not local to KDC
[15321] 1387302064.610443: Requesting tickets for ldap/dc001.example.org@EXAMPLE.ORG, referrals off
[15321] 1387302064.610479: Generated subkey for TGS request: rc4-hmac/3291
[15321] 1387302064.610498: etypes requested in TGS request: aes256-cts, aes128-cts, des3-cbc-sha1, rc4-hmac
[15321] 1387302064.610636: Sending request (1650 bytes) to EXAMPLE.ORG
[15321] 1387302064.610987: Initiating TCP connection to stream 172.16.50.2:88
[15321] 1387302064.611340: Sending TCP request to stream 172.16.50.2:88
[15321] 1387302064.611909: Received answer from stream 172.16.50.2:88
[15321] 1387302064.612016: Response was from master KDC
[15321] 1387302064.612042: TGS request result: -1765328316/Realm not local to KDC
ldap_sasl_interactive_bind_s: Local error (-2)
        additional info: SASL(-1): generic failure: GSSAPI Error: Unspecified GSS failure.  Minor code may provide more information (Realm not local to KDC)

The odd thing that I see here is that EXAMPLE.ORG is not IP address 172.16.50.2.  That IP address belongs to dc001.project1.example.org.  Any thoughts on that?

Thanks!
- Alex