Just did a fresh install of MySQL (latest version) onto Redhat Linux 7.2, and it installed great from the server and client RPM files. Only problem is i tried changing the root password like in the tutorial from here:

mysqladmin -u root password "newpassword"

and i get back an error:

"error: 'Access denied for user: 'root@localhost' (Using password: NO)'

so i tried:

mysqladmin -u root -p password
and it asks for a password then, and i enter one, and once again i get the same error as before:
"error: 'Access denied for user: 'root@localhost' (Using password: YES)'

Tried all sorts of variations with mysqladmin password setting (with root as username and without, etc) and each time i get this access denied error. This is a fresh install (tried several fresh installs in fact), everything seems to work but this, it's like root doesn't exist to mysql or have access to change passwords for some reason. Any ideas?