Sorry for the delay in response, but I had to run off yesterday... Perhaps you could check whether you are allowing self-signed certs:
zmlocalconfig -s ssl_allow_untrusted_certs
If that returns false, please run:
zmlocalconfig -e ssl_allow_untrusted_certs=true
If that doesn't allow you to recreate the cert, have you tried running a local upgrade (to the same version)? I've found in the past that upgrading to the same version can often recover from unforeseen/odd issues.
Please let me know if this resolves the issue.