...on Ubuntu Lucid. One link on this topic is http://dev.mysql.com/doc/refman/5.0/en/resetting-permissions.html.

Conceptually, here's what I found I had to do:

1. Get root.
2. Stop mysqld.
3. Start mysqld by hand and in the background in a special mode to grant rights to mess with passwords.
4. Launch mysql command-line application.
5. Fix the password.
6. Bounce mysqld.
7. Try it out.

Here's an illustration of some of what went on:

	russ@tuonela:~> sudo bash
	root@tuonela:~> /etc/init.d/mysql stop
	root@tuonela:~> /usr/sbin/mysqld --skip-grant-tables &
	root@tuonela:~> /usr/bin/mysql -u root mysql
	Welcome to the MySQL monitor. Commands end with ; or \g.
	Your MySQL connection id is 1
	Server version: 5.1.41-3ubuntu12.6 Ubuntu)

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

	mysql> UPDATE user SET password=PASSWORD('snagglepuss') WHERE user='root'; FLUSH PRIVILEGES
	ERROR 1046 (3D000): No database selected
	Query OK, 0 rows affected (0.00 sec)
	mysql> exit
	Bye
	root@tuonela:~> /etc/init.d/mysql start
	root@tuonela:~> ps -ef | grep [m]ysql
	mysql    2751   2703  0 10:57 pts/1    00:00:00  /usr/sbin/mysqld --skip-grant-tables
	root@tuonela:~> kill -9 2751
	root@tuonela:~> /etc/init.d/mysql start
	root@tuonela:~> /usr/bin/mysql -u root -p
	Enter password: snagglepuss
	Welcome to the MySQL monitor. Commands end with ; or \g.
	Your MySQL connection id is 36
	Server version: 5.1.41-3ubuntu12.6 Ubuntu)

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

	mysql> quit

Clearly, once you've got the root password, you can go back in and reset any common user's password. But, you've got to have root access.

Here's my experience from the next time this happened (March 2012):

$ sudo bash
$ /etc/init.d/mysql stop
$ mysqld_safe --skip-grant-tables &
$ mysql --user=root mysql
mysql> update user set password=PASSWORD('new-password') where user='root';
mysql> flush privileges;
mysql> exit;
$ ps -ef | grep [m]ysql
$ kill -9 (the pid associated with mysqld_safe)
$ /etc/init.d/mysql start
$ mysql -u root -p
Enter password: (new-password)

Here's how to set up for a common user (rather than root) to create, read, update and delete database tables. Here we start logged in and running the command-line utility as root and list the current users.

	mysql> select user from mysql.user;
	+------------------+
	| user             |
	+------------------+
	| root             |
	| debian-sys-maint |
	| root             |
	| root             |
	+------------------+
	4 rows in set (0.00 sec)

	mysql> create user 'russ'@'localhost' identified by 'test123';
	Query OK, 0 rows affected (0.00 sec)

	mysql> grant all on *.* to 'russ'@'localhost';
	Query OK, 0 rows affected (0.00 sec)

	mysql> select user from mysql.user;
	+------------------+
	| user             |
	+------------------+
	| root             |
	| debian-sys-maint |
	| root             |
	| russ             |
	| root             |
	+------------------+
	5 rows in set (0.00 sec)

	mysql> quit
	Bye

Later, ...

	russ@tuonela:~> mysql -u russ -p
	Enter password: test123
	Welcome to the MySQL monitor.  Commands end with ; or \g.
	Your MySQL connection id is 41
	Server version: 5.1.41-3ubuntu12.6 (Ubuntu)

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

	mysql> quit
	Bye