Did you all three change the hostname of the MC ? The option was disabled by Olivier (diserens) previously probably because it messed up with the DB sync. Here I suppose we change the password using wizard for all account (root@localhost, mailcleaner@%, etc...) but not for this specific one as we don't know it previously.
Could someone do a simple test ? Change again your hostname for "mailcleaner". Then restart all MC and test if the DB can be accessed. I'm almost sure it will work correctly. In this case: two solutions
1) Keep mailcleaner as "internal" hostname and use your DNS to give a "real" name
2) I'll explain the problem to the team and ask for a corrective, so you'll probably have to wait..
3) (Hmmm yes there was two before i began this list...) Change the password for the account firstname.lastname@example.org
in the DB.
To do this you'll have to check the request i use in /usr/mailcleaner/www/lib/configurator/dbpass.inc
Then reapply this in /usr/mailcleaner/bin/mc_mysql -m master