How?
I agree, this is a missing feature.  I just moved from a 4 year old server with cPanel to a new server with Plesk, there are a few things I liked better about cPanel including this, but in general I am happy with the swtich.  
So, how do you do it?
I tried something like this to create the user in the database in Plesk 8.2.0 with MySQL v 14.12 Distrib 5.0.22 on a current CentOS Linux distro.  
It would be nice if it was a simple drop down selection, but this did work for me:
(note, you need to replace 'name_of_new_database','user_name' with the right values for you).  All of this would be at the command line:
mysql -u admin -p
  <type password>
  use mysql;*********** 
  select * from db;** 
   INSERT INTO db VALUES('localhost','name_of_new_database','user_name','Y','Y','Y','Y','Y','Y','N','Y','Y','Y','Y','Y','Y','Y','Y','Y','Y');
Then you need to let Plesk know it is there:
	use psa;
*** select * from data_bases;
//In what is printed, look for the new database you want to use and its ID number.  e.g.  9.
select * from db_users;
//In what is printed, look for the login you want to use and its account_ID number.  e.g.  18.
INSERT into db_users VALUES('','<LOGIN_NAME_GOES_HERE>','18','9');
//May not be needed, I didn't need to flush or restart.
 flush privileges;
That should do it.