Quase encontrei e apresentei a ajuda encontrada aqui link .
Simplesmente fazendo
dpkg -P --force depends <packages who fail>
Mais informações sobre esses argumentos: link
E depois de instalá-lo com o aptitude
sudo aptitude install mysql-server-5.1
Não é o caminho mais limpo, mas não há mais erros!