Well, it suddenly started working later in the day. I have no idea what caused the original issue.
If you have multiple macs, you can export the certificate and import it on another machine. That worked for me.
If you only have access to the one mac... wait four hours, cross your fingers and try again?