The certificate table does not contain enough valid certificates

We are trying to add a new server to our existing domino domain. We have registered the new server using the Domino Admin, when we go to the new server and use the Server setup we get the error “the certificate table does not contain enough valid certificates to verify the public key of its owner” 20 percent of the setup was complete, setup failed processing.

We are new to setting up and managing lotus domino servers and after hitting our heads against the wall decided it is time to ask for help.

Thanks in advance