not using password but denied (using password: YES)?

[Clint Alexander]

I'm not sure if I just have been gone for a while and missed some meeting, but I ran into a strange situation.

A default install of MySQL 5.1.59-ius-log

[root@server ~] mysql
ERROR 1045 (28000): Access denied for user 'root'@'localhost' (using password: YES)

but I'm not using a password... So check this out...

[root@server ~] mysql -p
Enter password: <just press Enter>
Welcome to the MySQL monitor. Commands end with ; or \g.
Your MySQL connection id is 265
Server version: 5.1.59-ius-log Distributed by The IUS Community Project
... yada yada.

So it works with a blank password but not when connecting without the password. When using no password, the error report reads 'using password: YES'.

I've deleted the root@localhost and recreated without a password a few times and it didn't fix it:
CREATE USER 'root'@'localhost';
I've even flushed privs every time just because:
FLUSH PRIVILEGES;
... and I've tried to reset the password:
SET PASSWORD FOR 'root'@'localhost' = ''

I have this problem with other usernames as well when setup like this.

So, I'm a little confused. Does this happen to anyone else or does anyone have an idea what causes it?