depois de pesquisar um pouco mais, me deparei com isso, o que fez o truque;
sudo service mysql stop
sudo /usr/bin/mysqld_safe --skip-grant-tables &
mysql -h localhost
De lá, eu pude conectar ao mysql. Então:
update user set plugin='mysql_native_password' where user = 'root';
Depois de reiniciar o serviço, consegui me conectar com o usuário root.