Depois de muitas tentativas, incluindo destruir a instância na EC2 e criar uma nova continuava com esse erro no primeiro login que não permitia eu criar uma senha, nem logar com a senha padrão.
Resolvi o problema limpando tudo em /var/lib/mysql
OBS: isso exclui todos os dados no servidor MySQL
$ sudo rm -R /var/lib/mysql
