I’ve got it working with SSL again. I had restarted HASS several times and it made no difference (even though OpenSSL was saying the certificate was valid), what worked was adding certificate: auto to my mqtt configuration and restarting HASS. The configuration now looks like this:
mqtt:
broker: *.cloudmqtt.com
port: 2****
certificate: auto
username: *****************
password: *****************
Somehow, with the new SSL certificate configuration, this is now needed when it was not needed before. I tried changing the configuration back, in case this was just coincidence and it had been fixed anyway, but it broke again with the same SSL error.