Cannot join Win7 workstations to Win2k8 domain

I am trying to connect a Windows 7 Ultimate machine to a Windows 2k8 domain and it's not working. I get this error:

Note: This information is intended for a network administrator. If you are not your network's administrator, notify the administrator that you received this information, which has been recorded in the file C:\Windows\debug\dcdiag.txt.

DNS was successfully queried for the service location (SRV) resource record used to locate a domain controller for domain "example.local":

The query was for the SRV record for _ldap._tcp.dc._msdcs.example.local

The following domain controllers were identified by the query:
dc1.example.local
dc2.example.local

However no domain controllers could be contacted.

Common causes of this error include:

• Host (A) or (AAAA) records that map the names of the domain controllers to their IP addresses are missing or contain incorrect addresses.

• Domain controllers registered in DNS are not connected to the network or are not running.

The client is in an office connected remotely via MPLS to the data center where our domain controllers exist. I don't seem to have anything blocking connectivity to the DCs, but I don't have total control over the MPLS circuit, so it's possible that there's something blocking connectivity.

I have tried multiple clients (Win7 Ultimate and WinXP SP3) in the one office and get the same symptoms on all of them.

I have no trouble connecting to either of the domain controllers, though I have, admittedly, not tried every possible port. ICMP, LDAP, DNS, and SMB connections all work fine.

Client DNS is pointing to the DCs, and "example.local" resolves to the two IP addresses of the DCs.

I get this output from the NetLogon Test command line utility:

C:\Windows\System32>nltest /dsgetdc:example.local
Getting DC name failed: Status = 1355 0x54b ERROR_NO_SUCH_DOMAIN

I have also created a separate network to emulate that office's configuration that's connected to the DC network via LAN-to-LAN VPN instead of MPLS. Joining Windows 7 computers from that remote network works fine.

The only difference I can find between the two environments is the intermediate connectivity, but I'm out of ideas as to what to test or how to do it. What further steps should I take?

(Note that this isn't actually my client workstation and I have no direct access to it; I'm forced to do remote hands access to it, which makes some of the obvious troubleshooting methods, like packet sniffing, more difficult. If I could just set up a system there that I could remote into, I would, but requests to that effect have gone unanswered.)

2011-08-25 update:
I had DCDIAG.EXE run on a client attempting to join the domain:

C:\Windows\System32>dcdiag /u:example\adminuser /p:********* /s:dc2.example.local

Directory Server Diagnosis

Performing initial setup:
   Ldap search capabality attribute search failed on server
   dc2.example.local, return value = 81

This sounds like it was able to connect via LDAP, but the thing that it was trying to do failed. But I don't quite follow what it was trying to do, much less how to reproduce it or resolve it.

2011-08-26 update:
Using LDP.EXE to try and make an LDAP connection directly to the DCs results in these errors:

ld = ldap_open("10.0.0.1", 389);
Error <0x51>: Fail to connect to 10.0.0.1.
ld = ldap_open("10.0.0.2", 389);
Error <0x51>: Fail to connect to 10.0.0.2.
ld = ldap_open("10.0.0.1", 3268);
Error <0x51>: Fail to connect to 10.0.0.1.
ld = ldap_open("10.0.0.2", 3268);
Error <0x51>: Fail to connect to 10.0.0.2.

This would seem to point fingers at LDAP connections being blocked somewhere. (And 0x51 == 81, which was the error from DCDIAG.EXE from yesterday's update.) I could swear I tested this using TELNET.EXE weeks ago, but now I'm thinking that I may have assumed that its clearing of the screen was telling me that it was waiting and not that it had connected.

I'm tracking down LDAP connectivity problems now. This update may become an answer.