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
Code:
/etc/init.d/ssh restart
3. su - zimbra
4. Be sure zimbra's ssh port is set to 22
Code:
zmprov ms server.domain.com zimbraRemoteManagementPort 22
5. Generate new ssh keys
Code:
cd /opt/zimbra/bin/
./zmsshkeygen
6. Deploy the keys
To test this, you can run the following command:
-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