Aparentemente, o problema foi causado pela falta de espaço de armazenamento durante a primeira tentativa: o MySQL tentou criar um arquivo de dados, que falhou devido a espaço insuficiente e deixou um arquivo de dados corrompido, bem como um arquivo de configuração apontando para ele .
IIRC minha primeira tentativa foi em sudo apt-get remove
MySQL e reinstalar, o que deixou o arquivo de dados defeituoso e a configuração por trás, então a próxima instalação iria pegá-lo e falhar da mesma maneira.
Aparentemente, mesmo um sudo apt-get purge mysql-server-5.5
subseqüente não removeu esses itens. A seguinte sequência de comandos finalmente fez o truque para mim:
sudo apt-get purge mysql-server-5.5
sudo rm -R /etc/mysql
sudo rm -R /var/lib/mysql
sudo apt-get install mysql-server
Depois disso, o MySQL apareceu e eu pude acessar o console do MySQL.
Importante: Isso irá apagar permanentemente todos os dados do MySQL em seu sistema. Faça isso somente em uma nova instalação ou se você estiver ciente das conseqüências.