I had a similar problem. In my case the reason was that I'm using mySQL 4.1.x and non-empty password field. MySQL manual explains the situation and fix as follows:
2.5.1 Upgrading From Version 4.0 to 4.1
...
The password hashing mechanism has changed in 4.1 to provide better security, but this may cause compatibility problems if you still have clients that use the client library from 4.0 or earlier. (It is very likely that you will have 4.0 clients in situations where clients connect from remote hosts that have not yet upgraded to 4.1). The following list indicates some possible upgrade strategies. They represent various tradeoffs between the goal of compatibility with old clients and the goal of security.
- Don't upgrade to 4.1. No behaviour will change, but of course you cannot use any of the new features provided by the 4.1 client/server protocol, either. (MySQL 4.1 has an extended client/server protocol that offers such features as prepared statements and multiple result sets.) See section 11.1.4 C API Prepared Statements.
- Upgrade to 4.1 and run the mysql_fix_privilege_tables script to widen the Password column in the user table so that it can hold long password hashes. But run the server with the --old-passwords option to provide backward compatibility that allows pre-4.1 clients to continue to connect to their short-hash accounts. Eventually, when all your clients are upgraded to 4.1, you can stop using the --old-passwords server option. You can also change the passwords for your MySQL accounts to use the new more secure format.
- Upgrade to 4.1 and run the mysql_fix_privilege_tables script to widen the Password column in the user table. If you know that all clients also have been upgraded to 4.1, don't run the server with the --old-passwords option. Instead, change the passwords on all existing accounts so that they have the new format. A pure-4.1 installation is the most secure.
/Lassi