Solved!
We spent a lot of time trying to find this fault and trying to figure out if it was an OD AD or client Mac problem, we looked closely at our AD DNS as we had also noticed that our Global Catalog was slow to respond.
We then remembered that Openhive/captia had asked us to turn off our DNS dynamic updates (last November) as they said that our DNS was trying to update their DNS server, we did this, and there seemed to be no problem, PCs would bind OK, DNS worked fine. So having tried almost everything we could think off we turned on the DNS dynamic updates, and within half an hour our Global catalog worked and the Macs bound to the AD!
Here's Reg setting Captia sent us, we have now deleted this DWORD Value
Click Start, click Run, type regedit, and then click OK.
Locate and then click the following registry subkey: HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\ Tcpip\Parameters
On the Edit menu, point to New, and then click DWORD Value.
Type DisableDynamicUpdate, and then press ENTER two times.
In the Edit DWORD Value dialog box, type 1 in the Value data box, and then click OK.
Note By default, the DNS update is enabled (0).
Exit Registry Editor.