If you can place the Domain server on the same subnet as the ones that do connect maybe using a secondary nic and if this works could mean you have some firewall policy or other rules.