Forgive me if I'm asking the obvious, but it's always best to cover the basics first. Are you sure the DB username and password are right? Does the database already exist?

I`m pretty sure, I`ve double checked, I run into this problem everytime I am hosted.

Every time you are hosted? What do you mean? Surely your site needs to be hosted somewhere to get it working... Unless you run your own server...

I mean, when I am hosted with a subdomain. Usually I want to set up b2 or b2evolution and the mysql host is "localhost" it doesn`t work, but if it`s an outside source then it`s perfectly fine.

How are you setting the config up? Through the installation routine or by manually editing the file?

I tried the installation routine, then I tried manually editing the file...what do you do after you edit the file?

Save it, the upload it to the /conf folder. I have to say, it sounds very much like it's a problem with your server somewhere...

Are you sure? This has happened four times with four different accounts.

No I'm not sure. My money is still on either a config error, or the database not existing...

localhost may not be the right setting here. check with your hosting provider.

Maybe its: localhost.localdomain

I asked my host, she said it was localhost and I tried localhost.localdomain which didn`t work either :(

can you log into MySQL using any other method? Do you have shell or terminal access to your server? If so, try connecting, and typing this at the prompt:

mysql -h localhost -u YOURUSERNAMEGOESHERE -p

and press return. (Replace YOURUSERNAMEGOESHERE with your MySQL username.) It'll prompt for your password, so type that in. What happens?

If you don't have shell access, do you have phpMyAdmin, or any other program where you can log in and do MySQL stuff? When you're in phpMyAdmin, it should say "database on hostname" at the top of the page. What do those say?

Somehow, there's a discrepancy between the name that is entered in b2evolution, and the reality of where your server is. But we certainly wont' solve the problem by just repeating over and over, "are you sure it's localhost?" "yes, i'm sure" "is that what you entered" "yes, that's what i entered."

I had this problem, but resolved it by doing the following:
Removing and re-adding the user to the database with proper permissions.
Manually editing the config file.
Closing all browser windows and clearing the cache.
Going to www.mysite.com/admin and running the initial database setup there.

Everything seems to have gone fine after that.