Wrong password

I’m having a very interesting problem. We have two IP ranges connected through a Cisco router. For some reason the folks on one side can’t logon to the domain in the other side(By the way I only have servers on one side of the network, and it was working okay). It says that the password is incorrect or the user has been lock. But neither is the case since I use there user in the network side in which the server is and they don’t have any problem with their password. What make it more interesting is that if I put a name that doesn’t exists in the domain it will tell me so. The problem seems to be with the password and it’s only for NT. For Netware servers they can log without any problem. Any ideas????