The error message is very generic. It could be the host is denied access, the user is denied access or wrong password.
For example, you might have "root@hostname" allowed access. Using "root@hostname.domainname" would be denied access.
The "root" user for mysql has no relation to the "root" user for Linux. By default, just after installation, the root account doesn't have a password. Simply press enter after "mysql -u root -p", you may have access. If that doesn't work, look in the manual (or Google) for options to start the mysqld server with, that will allow you access to reset password. This post may work as well
http://www.linuxquestions.org/linux/...ssword_recovey
If you just installed mysql, make sure you read the MySQL manual. At least the section on security. By default, there is a demo table with global access. Delete it. The root account doesn't have a password. Be sure to create a password for it.