RESOLUTION
SYMPTOMS:
Newly created database users works fine, but the old ones that were created before MySQL upgrade cannot connect to it's databases due to password error.
CAUSE:
Most probably the problem is caused by 'mysqld' using new password notation.
RESOLUTION:
Set old_passwords option in /etc/my.cnf in [mysqld] section and restart MySQL:
old_passwords=1
Update passwords for the MySQL users that were created by Plesk in 'mysql' database using the command below: