I am moving servers and I am unable to login when I use a password on my
site. What I mean is I have a site that is password protected and the
logins and passwords are located in a MySQL database.

On the old site I use the following:
$sql = "SELECT *
FROM users
WHERE user_id = 'houghi'
AND user_password = PASSWORD('qwerty')";

This works perfectly. It finds the user, even though the database has
the password saved as e.g. 123fb41647a4ad66

However on the new server I am unable to do this. It does not find the
user. I am able to do the following:
$sql = "SELECT *
FROM users
WHERE user_id = 'houghi'
AND user_password = '*1A6E805D1E699D8AE2566EE092D3FBA'";

With the PASSWORD('password') it does not work. Without it and using
what is exactly in that field, it does work.
I do not want to be using plain text passwords. So what must I do to
correct this?

I use phpMyAdmin to change the password and select the PASSWORD as
Function there. That does the following:
UPDATE `tph`.`users` SET `user_password` = PASSWORD( 'azerty' ) WHERE
CONVERT( `users`.`user_id` USING utf8 ) = 'houghi' LIMIT 1 ;

I do all this in phpMyAdmin, so no other things involved, like strange
php code or javascripts.

I do see a difference between the old and the new server. The old server
gave passwords like 123fb41647a4ad66 and the new one has passwords like
*1A6E805D1E699D8AE2566EE092D3FBA
So something has changed, but I have no idea how to correct it. MySQL
version is 5.0.51a running on openSUSE 11.0

I have done several searches, but I end up with changing the password
for MySQL itself and that is not what I need.