Possible Causes and Solutions:
The client has not keylogged in. Make sure that the client is keylogged in. To determine if a client is properly keylogged in, have the client run nisdefaults -v (or run it yourself as the client). If
(not authenticated) is returned on the Principal Name line, the client is not properly keylogged in.
The client (host) does not have appropriate LOCAL or DES credentials. Run niscat on the client's cred table to verify that the client has appropriate credentials. If necessary, add credentials as explained in "Creating Credential Information for NIS+ Principals".
The keyserv daemon is not running. Use the ps command to see if keyserv is running. If it is not running, restart it and then do a keylogin.
While keyserv is running, other long running processes that make secure RPC or NIS+ calls are not. For example, automountd, rpc.nisd, and sendmail. Verify that these processes are running correctly. If they are not, restart them.