I had this issue crop up today using Z2MQTT 1.36.0-1 and the latest version of HA.
@radionerd solution worked. Puzzling has been working forever then suddenly this!
Hello! The following helped me: using a file editor, I edited the configuration.yaml file in the letter /homeassistant/zigbee2mqtt and rolled back the latest changes. For example, I removed the retention: line, which requires version 5 of the mqtt broker. You can also manually roll back the latest changes. After that, I saved the file and restarted the add-on.
2 years later this still worked! Thanks! For some reason the config tab in the add-on menu does not work properly so this is the best way to solve it.