Error in login in with root user in new mysql server
Please run the following:
mysql -uroot -pPa$$w0rd -ANe&quot;SELECT USER() ReqUserLogin,CURRENT_USER() AllowedUserLogin;&quot;
mysql -uroot -pPa$$w0rd -ANe&quot;SELECT user,host,password FROM mysql.user WHERE user='root'&quot;

The first query will show you two things:

USER() reports how you attempted to authenticate in MySQL
CURRENT_USER() reports how you were allowed to authenticate in MySQL

The second query will show you all root users. It is possible only one root user got the password embedded and left the other without one.
Run this query to assign the same password to all root users:
UPDATE mysql.user A INNER JOIN mysql.user B USING (user)
SET A.password=B.password WHERE A.password='' AND B.password&lt;&gt;'';
FLUSH PRIVILEGES;

While you are at this point, you may as well get rid of anonymous users:
DELETE FROM mysql.user WHERE user=''; FLUSH PRIVILEGES;

and disable public access to test databases
DELETE FROM mysql.db WHERE SUBSTR(db,4) = 'test';
FLUSH PRIVILEGES;

I wrote about this before:

Cannot drop anonymous user from mysql.user
Is this a normal set of MySQL privileges?
Limiting database security

UPDATE 2012-06-13 15:58 EDT
I think I understand the problem. Look back at your original command to create the password:
/usr/bin/mysqladmin -u root password Pa$$w0rd

In Linux, $$ stands for something. Just run echo $$ and see:
[root@... ~]# echo $$
30837
[root@... ~]# ps -ef | grep 30837
root      2354 30837  0 15:50 pts/0    00:00:00 ps -ef
root      2355 30837  0 15:50 pts/0    00:00:00 grep 30837
root     30837 30835  0 14:49 pts/0    00:00:00 -bash
[root@... ~]#

You should have done this:
/usr/bin/mysqladmin -u root password 'Pa$$w0rd'

Here is a working theory. Run that command echo $$ (let's pretend $$ is 30837)
Try to login like this:
mysql -u root password -p&quot;Pa$$w0rd&quot;

If this does not work, try this:
mysql -u root password -pPa30387w0rd

If this last one works, you have the password with the number embedded.
Here is how to change it to Pa$$w0rd:
mysql -u root password -pPa$$w0rd -e&quot;SET PASSWORD = PASSWORD('Pa$$w0rd');&quot;

Give it a Try !!!