Debian + MySQL = Failed to login

[YamiHoshi]

On every VPS (installation), when I install a Debian server, it never let me to connect to MySQL.

[root@client319 ~]#mysql -p
Enter password: 
ERROR 1045 (28000): Access denied for user 'root'@'localhost' (using password: YES)
[root@client319 ~]#

Password is right, I know that over 9000%.
I reseted it over a billion times in the past, but still no success.

Could someone now answer this question?
Looks like everyone ignored my previous 2 questions.

Update1:
Found out that Debian version of MySQL doesn't ship with the user "root" by default.
Fixed that, and it's working.