Let me add a few details I just found out:
I believe there must be some kind of problem with the MySql Linux implementation that comes toghether with the XAMPP package (At least version 1.7+).
I found that when I try to connect to my server from my WinXP to the MySql (On the RH) it works just fine (through a GUI Query Browser), but when I try this from a VM terminal (using the CLI mysql client) i can only log with empty password users.
I tried using the old_password function and even created a user with a password from the CLI, but when I got out of the client, I couldn't log back in with the newly created user (which, btw, worked fine from WinXP).
I tried all that at work (XAMPP 1.7.1), but then when I got back home I tried the same on an XAMPP 1.7 and the same thing happened.
My work configuration is the following:
WinXP hosting a RH VM both with XAMPP 1.7.1. On the WinXP I have MySQL query browser installed.