OK, I think I solved it.
Apparently, cyrus wasn't the only thing that failed. Basically everything that used those certificates failed.
I don't really understand what's going on, but apparently Openssl has been updated, and those certificates were older versions that are now discarded by openssl somehow?
I ended up creating new certificates and they work, everything seems to work with them, not just cyrus.
