Ubuntu Security :: Cannot Ssh To NFS-connected Machine / Permission Denied

I have, say, 10 machines, connected via NFS and NIS. There's a server which exports the /home using NFS, and exports the user names using NIS. All machines are working fine. I am able to ssh to the machines remotely and get my work done.Recently though, one of the machines (say M, for easy reference) would not allow any other machine on the NFS network [or outside the NFS network] to ssh into it. Every time an ssh attempt is made, 3 IP addresses [including the machine from which an ssh attempt was being made] are added to the /etc/hosts.deny file on M, and the error message on the other machine shows 'permission denied' after the password is entered. I tried using various options that ssh provides, but I cannot figure it out. I also tried uninstalling and reinstalling openssh-client and openssh-server on M, but it didn't change anything.

Another point to note is this: another user made use of M before, for a while, by disabling ssh passwords - so he could access M without having to enter his ssh password. That individual can still log in to M. All others who require to enter a password cannot ssh into M.