Windows 2003 Server domain controllers have "Microsoft network server: Digitally sign communications (always)" set to "Enabled" by default. This is likely causing the Macs to fail to authenticate with the "error = -5000".
To change this on a given domain controller, go to "Start" ->"Administrative Tools" -> "Domain Controller Policy" (not Domain Policy) and look for "Security Settings" -> "Local Policies" -> "Security Options" -> "Microsoft network server: Digitally sign communications (always)". It should show "Enabled" by default. Double-click on it and set to "Disabled". Then close the app and reboot the server. When it comes back up, the Macs should connect without difficulty.
This is the only setting that needs to be changed. Disabling the other similar settings will only weaken the security between all your Windows boxes.