NT: Erratic Domain authentication

Our WAN users have just started having this problem and I am unsure how to address it.

WAN Users OP systems are a mix of Win9x, XP, and 2000 clients. They log into our PDC (Win NT 4.0)using MS Client. Sometimes they are able to log in without any problems, more often than not they now have to enter their password, wait until they receive the “NO DOMAIN SERVER AVAILABLE” error, press cancel, and then OK in order to gain access to the domain!!!!

Any help or direction would be greatly appriciated.