I have had similar problems with exchange 2000
when I set a dns server that was not the dc.  Try
changing it on the remote client.  I even tried
the IP address, but it didn't like it.  Also,
there is a stupid thing with windows 2000 and
exchange that makes you delete tcpip from the
network connection and reinstall it.  You could
try that.  The two of those has always solved my
problems.  I don't leave the dc as the dns, but i
have had to set it as such to make a connection
at times.  I hope this helps,  Good luck.