Normal User cannot log on

[Anoop Rajendra <axr3845@omega.uta.edu>]

Hi, I have a rather strange problem. I have a cluster of machines where
authentication is governed by NIS. Root logs into all machines without
NIS. (Thank god for that). Now any new user I create also can log into
the other machine, only under the condition that I'm logged into the
main machine as root.
Meaning.

This works -
root@gecko: ssh -l nostromo gecko2

However this doesnt work -
nostromo@gecko: ssh gecko2

It gives me a "Host key Verification failed" error.

How i can solve the problem?

Thanks,
Anoop