Conclua a limpeza e reinstale.
Infelizmente, esta é a única resposta que consegui encontrar no período de tempo com que tive de lidar.
Estou tentando atualizar meu desktop ubuntu. Quando ele tenta atualizar o mysql-server-5.1, ele congela dizendo preparing to update mysql-server-5.1 .
Ele não me permite fazer outras atualizações, porque diz que as coisas estão quebradas e me diz para reinstalar isso.
Eu não uso o mysql-server, então eu ficaria feliz em apenas remover a coisa toda. Mas isso não me deixa fazer uma remoção.
Eu enfrentei uma questão semelhante desde hoje de manhã; de repente meu mysql-server-5.1 começou a dar problemas e eu não consegui removê-lo ou instalá-lo novamente.
Eu finalmente consegui remover o MySQL e todos os pacotes associados via synaptic depois de algumas tentativas. Não tenho certeza do que exatamente funcionou, mas agora estou reinstalando o LAMP sem problemas.