[mmorse]

Assuming you're using the standard ssh port:
1. Check /etc/sshd_config and be sure it's set to 22
2. stop/start/restart sshd

/etc/init.d/ssh restart

3. su - zimbra
4. Be sure zimbra's ssh port is set to 22

zmprov ms server.domain.com zimbraRemoteManagementPort 22

5. Generate new ssh keys

cd /opt/zimbra/bin/
./zmsshkeygen

6. Deploy the keys

./zmupdateauthkeys

To test this, you can run the following command:

ssh -vi .ssh/zimbra_identity -o strictHostKeyChecking=no zimbra@server.domain.com -p 22

-Shouldn't prompt you for a password at this point...then check the admin console mail queues area/servers/certificates.
If you continue to get that error please see this doc for some more ideas Mail Queue Monitoring - Zimbra :: Wiki