Encontrou a resposta e talvez seja útil para outra pessoa.
O problema é que, mesmo depois de desinstalar o servidor mysql para instalá-lo novamente e testá-lo, o sistema não me permitiu criar uma senha.
Então eu desinstalei usando sudo apt-get remove mysql-server
e depois disso sudo apt-get autoremove
, mas não foi o suficiente. O erro ainda estava lá.
O que resolveu a questão foi:
sudo apt-get remove --purge mysql-server mysql-client mysql-common
sudo apt-get autoremove
sudo apt-get autoclean
sudo apt-get update && sudo apt-get upgrade
Depois disso, comecei tudo de novo, e foi uma instalação limpa:
sudo apt-get install mysql-server
E o sistema me pediu para definir uma senha antes que a instalação terminasse.