Experimente os passos no link
O principal passo é adicionar as seguintes linhas na sua configuração do mysql (corretamente /etc/mysql/my.cnf). Isso basicamente desativa a segurança do mysql e o acesso à rede.
[mysqld]
# These let you safely reset the lost root password.
skip-grant-tables
#enable-named-pipe
#skip-networking
Reinicie o mysql e você pode fazer o seguinte sem uma senha.
mysql -u root
Lembre-se de alterar seu arquivo de configuração novamente depois de redefinir sua senha de root.
Método 2
Como você está usando o Ubuntu, abra /etc/mysql/debian.cnf
Você deve ver algo como seguir
[client]
host = localhost
user = debian-sys-maint
password = xxxxxxxxxx
socket = /var/run/mysqld/mysqld.sock
...
Tente seguir
mysql -u debian-sys-maint
com a senha nesse arquivo. Se isso te colocar no prompt do mysql, você pode redefinir sua senha root sem mexer no my.cnf.