I needed to reset the root mysql password on an Ubuntu 11.04 installation. The /etc/init.d script apparently used to have a reset-password option that no longer exists. Here's what I did.

Stop mysql daemon:

$ sudo service mysql stop

Start mysqld with --skip-grant-table option in one terminal:

$ sudo mysqld --skip-grant-table

Use mysql shell to reset root password:

$ mysql
Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 1
Server version: 5.1.54-1ubuntu4 (Ubuntu)

Copyright (c) 2000, 2010, Oracle and/or its affiliates. All rights reserved.
This software comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to modify and redistribute it under the GPL v2 license

Type 'help;' or '\h' for help. Type '\c' to clear the current input statement.

mysql> UPDATE mysql.user SET Password=PASSWORD('BlahBlah123') WHERE User='root';
Query OK, 3 rows affected (0.00 sec)
Rows matched: 3  Changed: 3  Warnings: 0

mysql> FLUSH PRIVILEGES;
Query OK, 0 rows affected (0.00 sec)

mysql> Bye

Find the process id of mysqld and kill it (not kill -9, that's always a last resort):

$ ps -e | grep mysqld
 4910 pts/1    00:00:00 mysqld
$ sudo kill 4910

Start up mysql normally:

$ sudo service mysql start