Can't connect to MySQL after configuration

Hello,

I've just configured MySQL for supporting nova as described here http://docs.openstack.org/trunk/openstack-compute/install/content/setting-up-sql-database-mysql.html

Then, I tested the connection to MySQL as as the user created by the MySQL instruction

GRANT ALL ON nova.* TO 'nova'@'%' IDENTIFIED BY 'yourpassword';

I get the following error:

ERROR 1045 (28000): Access denied for user 'nova'@'localhost' (using password: YES)

I'm pretty sure that the credentials I typed are correct.

In order to surpass the problem, I dropped the just created user and create again with:

GRANT ALL ON nova.* TO 'nova'@'localhost' IDENTIFIED BY 'yourpassword';

It works but it is not what I wanted because I want that the user can connect from any other server.

The point is that I tested exactly the same stuff on a different (previous) version of MySQL and it works as expected.

Version OK: mysql Ver 14.14 Distrib 5.1.41, for debian-linux-gnu (x86_64) using readline 6.1
Version NOK: mysql Ver 14.14 Distrib 5.5.22, for debian-linux-gnu (i686) using readline 6.2

Can anybody help me?