First check with the SQL query
SHOW VARIABLES LIKE 'old_passwords'
(in the MySQL command line client,
HeidiSQL or whatever frontend you like) whether the server is set to use the old password schema by default. If this returns old_passwords,Off you just happen to have old password entries in the
users tables. The MySQL will use the old authentication routine for these accounts. But you can simply set a new password for the account and the new routine will be used.
You can check which routine will be used by taking a look at the
mysql.users table (with an account that has access to that table)
SELECT `User`, `Host`, Length(`Password`) FROM mysql.user
This will return 16 for accounts with old passwords and 41 for accounts with new passwords (and 0 for accounts with no password at all, you might want to take care of those as well).
Either use the user managements tools of the MySQL front end (if there are any) or
SET PASSWORD FOR 'User'@'Host'=PASSWORD('yourpassword'); FLUSH Privileges