Eu encontrei a solução para esse problema. Eu precisava desinstalar completamente o MySQL, seus bancos de dados e configuração, e restaurar a partir de backups. Isso foi realizado com:
apt-get remove mysql-client-5.5 mysql-client-core-5.5 mysql-common mysql-proxy mysql-server-5.5 mysql-server-core-5.5
e
apt-get purge mysql-client-5.5 mysql-client-core-5.5 mysql-common mysql-proxy mysql-server-5.5 mysql-server-core-5.5
e, em seguida, reinstalar o servidor mysql.
Era uma solução extrema, mas o MySQL estava extremamente quebrado.