MySQL - ERROR 1045 - Access denied

In some way I have managed to get this error when I try to access into MySQL via the command line:

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

I have tried resetting the password without any luck using this HowTo.

I have uninstalled mysql completley and reinstalled but I still get asked for a password. I have no idea why this is the case!

Can someone please help me get a default install of MySQL.

Environment

Fedora Core 10, Full Root Access, Apache and PHP installed

Thank you for any help!!

EDIT

To all those that would like to save themselves a few hours of "blood coughing" - when you uninstall MySQl completely delete everything that is left behind. If you don't do this, it will never be a FRESH install.

If you actually have set a root password and you've just lost/forgotten it:

1. Stop MySQL

2. Restart it manually with the skip-grant-tables option: mysqld_safe --skip-grant-tables

3. Now, open a new terminal window and run the MySQL client: mysql -u root

4. Reset the root password manually with this MySQL command: UPDATE mysql.user SET Password=PASSWORD('password') WHERE User='root'; If you are using MySQL 5.7 (check using mysql --version in the Terminal) then the command is:

   UPDATE mysql.user SET authentication_string=PASSWORD('password')  WHERE  User='root';
   

5. Flush the privileges with this MySQL command: FLUSH PRIVILEGES;

From http://www.tech-faq.com/reset-mysql-password.shtml

(Maybe this isn't what you need, Abs, but I figure it could be useful for people stumbling across this question in the future)

Try connecting without any password:

mysql -u root

I believe the initial default is no password for the root account (which should obviously be changed as soon as possible).