strivewind

it is indeed a very strange problem you are encountering.  Have you tried to un-join both of the workstations from the domain and re-join them back to the domain?  Also check your DNS server to see if there is anything not right.   Such as, if both of the workstations are registered correctly in the Forward Lookup DNS record on the DNS server, etc.  Please let us know what you find.