As you may have guessed it is a permission thing.
The problem is that the permissions have not been seen to connect from localhost. In mySQL there is an option on accounts as on the domain from where the user can access the server.
The users are either connected to the server as either:
(they are treated as completely different users, in this respect)
1) user@domain.com or user@localhost
or
2) user (direct connection)
PHP connects using the first way. This is why you can log in directly to MySQL but not using PHP.
I cant find my manual, but im sure you will find an example of this in the manual and a way to fix it easily.