Apparently PLESK does not support this, you have to create a new user with each database.
To get around this you (after letting PLESK create the database and it's initial user) bypass PLESK and handle it directly through the MySQL interface.
So,
1. If this is a remote machine use SSH to log into the server.
2. get into the mysql command line:
mysql -u usernamehere -p
it will prompt you for the password. Then you should be at a prompt that looks like
mysql>
3. you want to use the MySQL database so type: use mysql
4. then use the GRANT command to add a user to the database you want to add a user to.
example:
GRANT ALL ON MYDATABASE.* to 'usernamehere'@'%' IDENTIFIED by 'userpasswordhere';
don't forget the ; mysql will not execute the statement until it sees a ; it will just consider <enter> as a carriage return.
please note that the above statement will give full permissions on the database to that user from any location local or remote. You can check out the specifics on the grant command at http://dev.mysql.com/doc/refman/5.1/en/grant.html and see how to restrict permissions if needed.
I hope this helps.
Just as a note, you will not see this user as a user when you are in plesk but you will be able to connect with this user using PHP, MySQL Administrator, etc...
You can modify your plesk database if it is on your local server, and add an association between the user and the database and then this user will show up in PLESK also, but I have not tried this because I do not have access to my PLESK database. If I get access to it and can try it I will post the results.
-Cheers