If you are getting the above error during installation, this means either:

1. One or more of the following is wrong in your config.php file:
$servername (except in rare cases, this should almost always be left as 'localhost' or '127.0.0.1')
$dbusername
$dbpassword
$dbname

If you are unsure of what the appropriate values are then you will need to ask your web host.

2. Or that this db user is not assigned to that database or does not have permission to access MySQL to create or access a database. You may need to first manually create the database and assign the db user to it. Since each web host is different, if you do not know how to do this then contact your web host for help.

3. Or you are running MySQL 4.1.x. As of MySQL 4.1.X there is a new password hashing system. PHP4 does not have builtin support for it as of yet, however PHP5 does. In order for your old PHP4 MySQL clients to be able to connect to the MySQL 4.1.X database you need to set an OLD_PASSWORD. You should be able to run the following Query to make it possible for PHP4 to access the MySQL 4.1.X database.

SET PASSWORD FOR 'username'@'localhost' = OLD_PASSWORD('password');

More info is here:
http://dev.mysql.com/doc/mysql/en/password-hashing.html