Error: 'Access Denied For User 'root'@'localhost'

I've used mysql on an XP machine before, but only a little. I installed Fedora core 5 on this machine (i386) and have mysql 5.0 running.

I understand that this is a common problem and I have been searching for a solution for a few days now.

When I was configuring Fedora using this guide (FYI: I only installed what I needed), I used this command to set the root password (assuming that I was using 'root' as my password):
mysqladmin -u root password root
Then, I tried this command to login (as instructed by the guide I was following):
mysqladmin -h localhost -u root password root
This is where I got the error:
mysqladmin: connect to server at 'localhost' failed
error: 'Access denied for user 'root'@'localhost' (using password: NO)'

Now, I have tried many methods to fix this. I tried every method to reset the root password as instructed by the mysql documentation. I also installed Fedora core 5 on another hard drive at home to see if I would still get the same error and I did. I know that localhost is the correct host name and the mysql service was running while I was trying to login. I've read a lot of post here already and nothing has helped me.