パスワード忘れた場合のウチで今回成功した再設定手順です。
ubuntu 12.04 LTS
mysql Ver 14.14 Distrib 5.5.28

# mysqlは全て停止
sudo /etc/init.d/mysql stop
sudo killall mysqld

# セーフモードのような？起動方法
#  mysqld_safeの位置はディストリやmysqlインストール時の設定で各人で異なるかと
sudo /usr/bin/mysqld_safe -u root --skip-grant-tables &
mysql mysql

# ココでrootのパスを空値で設定
# この時点でも設定できるはずらしいのですがウチでは上手く行きませんでした
mysql> UPDATE user SET Password='' WHERE Host='localhost' and User='root';
FLUSH PRIVILEGES;
# 一旦はmysqlを抜けます
exit

mysqladmin password -u root
# ココでパスワードを再設定
New password: 
Confirm new password:

# コレで次回からは新しく設定したパスワードでログイン出来るはずです
mysql -u root -p

参考先サイト様
http://l-w-i.net/t/mysql/passwd_001.txt

ubuntu10.04 のパスワード忘れた時メモ
はい。
10.04 LTS使用です。はい、サポート切れですかね。。。
前にログインしてた頃は切れてなかった時期のような。それだけ間が空いていればパスワード忘れもむべなるかなという。
忘れ一日目はひたすら色々なパスワードを試して終わりました。(ずっと連続で試せるとか・・・)
忘れ二日目はsafemodeでも起動できることに気づき、それで起動してみたら
root@hagge #~

はい、rootで入れたおかげで後はもうpasswdで解決しました。