Eu enfrento sérios problemas ao tentar instalar o Mysql 5.5 no Ubuntu 12 hoje. Siga estas etapas se você estiver tendo o mesmo problema.
Primeiro, atualize a lista de pacotes disponíveis para o seu sistema:
$ sudo apt-get update
Agora vamos limpar a casa (aviso: isso irá deletar seus dados, fazer backup de tudo):
$ sudo apt-get remove --purge mysql-client-5.5 mysql-client-core-5.5 mysql-common mysql-server mysql-server-5.5 mysql-server-core-5.5
Finalmente, você está pronto para uma instalação limpa:
$ sudo apt-get install mysql-server
Feliz hackeamento!