**Most** shared hosting uses localhost for mysql, but that could definately be a problem. Additionally,
Access denied for user 'localhost' (using password: YES)...
Right now it is set up to login to mysql through localhost, root (username), and my password...
Leads me to believe you have something switched up in your variables. There are four basic things required to connect to mySQL. The database server, the database name, the mySQL user name, and password. I have used arbitrary $variables below, as an example.
$dbhost = 'localhost';
// or it could be mysql.example.com, as arms suggests
$db = 'The_name_of_the_database';
$db_user = 'the_mysql_user_name';
$db_pass = 'the pass';
Many things can cause this error - trying to connect to a database that doesn't exist, or one that this user doesn't have permissions for, or connecting to an incorrect server, or of course typos in the user name and password (there are others too.) But in your case, you are somehow using "localhost" as a user name. In my example, if you have this,
$dbhost = 'localhost';
$db_user = 'localhost';
.. it's likely going to generate that error.
If you check your database creation, you will probably already know
the database server name if you look for it. Most hosting CP's have a "create database" function, and if you don't see "connect to your database at mysql.example.com" it's likely localhost. BUT-
once the database is created, usually you will find a place to create a database user
and set that user's password. Still not done - once you've created the database user, you have to follow any links on the user name (or checkboxes and submit to modify) to assign access permissions to a given database and set the table permissions for that user. (A note - not only is it dangerous to allow the user root to connect to an online database, most control panels won't let you. You can do it via SSH on a dedicated server, but it's a Very Bad Idea. Choose some other user name to connect to mySQL.)
One more caveat - the creation process through some control panels such as WHM, Cpanel, etc. will give you confusing names, check it very carefully. So if, for example, you create a database "test", it may prepend the name with the hosting account user name.
So if your hosting account for some domain is "abc123", the actual database name will be abc123_test. The same would be true of user names - abc123_username. These are fairly easy to spot as (most of them) they won't allow you to use underscores in the DB/user names. Just be sure to use the prepended versions in your scripts.
Review all that, check your script variables, it should just work. :-)