O problema está resolvido agora.
Descobrimos que nosso programa de backup "mysqlhotcopy" era o problema.
A causa é que mysqlhotcopy bloqueia, como eu posso ver, em uma declaração todas as tabelas de todos os bancos de dados quando chamados sem parâmetro de banco de dados, respectivamente todas as tabelas de um banco de dados quando chamado com parâmetro de banco de dados. Como nossos bancos de dados podem conter milhares de tabelas, isso se tornou impossível com a configuração atual do sistema.
Então eu escrevi um novo script mysqlhotcopy e o problema desapareceu até agora.