The error you describe sounds like it results from the
mysql_select_db() function. If that's the case, am I to assume your
mysql_connect() statement did not fail?
You specify the hostname, username, and password with the mysql_connect function. If that did not produce an error, then your account does exist and you can login. If you then get an error when you attemt to select a specific database, then yes, the problem is most likely that your mysql account does not have any privs on that database.
Make sure that your mysql_connect statement is actually successful. For example, if you use the '@' in front of the statement, you won't know it failed. Do something like this:
[PHP]
if (!$cnn = mysql_connect('localhost', 'mysql_user', 'mysql_password')) {
die("Great google-moogly! The database connection failed!");
}
[/PHP]
NO! You do not need a dedicated server, and I would not recommend one to you--unless I was selling dedicated servers. <g> If you really know what you are doing, and you can afford it, a dedicated server is nice to have, but you certainly don't need one. I'd also like to take this moment to shamelessly advertise my hosting services. I provide business-class, LAMP hosting for only $5/mo with everything you need to build PHP/MySql web applications.
Unsolved 
