Hi Zard,
do you have dedicated server or are you on a shared hosting machine?
Authentication has been changed in MySQL5, so using an old mysql client you wont be able to login to your mysql the usual way. Where do you host? Maybe your hosting company can provide you more information. Try running phpinfo(); and look for the mysql part. If you have mysql5 installed, the client should be 5.0.x too !
Regards,
eSEFEROVIC