Error establishing a database connection

I keep getting the following error message

“Error establishing a database connection
This either means that the username and password information in your wp-config.php file is incorrect or we can’t contact the database server at localhost. This could mean your host’s database server is down.
• Are you sure you have the correct username and password?
• Are you sure that you have typed the correct hostname?
• Are you sure that the database server is running?
If you’re unsure what these terms mean you should probably contact your host. If you still need help you can always visit the WordPress Support Forums.”

I have looked at the following video links to provide guidance, but neither of their approaches have worked.

http://www.optiniche.com/blog/view.php?v=wp-install&w=773&h=472
http://www.youtube.com/watch?v=6nse3Gdtvs4

http://www.blog.web6.org/install-wordpress-3-2-video-tutorial/

I have uploaded the wordpress files to the blog database in the public_html directory after editing the config.php file – i have tried a number of permutations

a) keeping the local host and all other names, user names and password
b) changing the database name and username and password to that of the remote host while keeping the local host as the msql host name
c) changing all the data inputs to that of the host site

I have checked with my host provider that the remote host data and names i am using are correct.

But to no avail. None of the videos, none of the installers, be it filezilla or others and none of the docs i have read give me an inkling as to what is wrong….