Execute este comando,
dpkg -l | grep -i mysql-server
Isso deve retornar algo assim.
ii mysql-server
ii mysql-server-5.6
ii mysql-server-core-5.6
Você quer este mysql-server-5.6
.
sudo dpkg-reconfigure mysql-server-5.6
Isso deve pedir uma nova senha e ela reinicializará as tabelas. Agora você pode se conectar assim ..
mysql -h localhost -u root -p
Enter password:
E essa é a maneira mais Ubuntu / Debian que eu encontrei para isso facilmente.