I hope this is in the correct place.
I am in a new enviroment that has about 50-60 Linux boxes and prior to me getting here, they would change the root password by logging into each box and changing the password....ugh!

I trying to setup on server which will have ssh client keys for password less access to all of the servers and on this box. I want to run the pdsh command to change the root passwd. We did this at a previous employer, but it was in place when I got there,so I'm not sure how it was done.

I currently have keys in place on a test box and can login, without issue, but when I try to do "pdsh -w machinename passwrd root" it just hangs... I'm sure I'm doing something wrong.

Since you are only connecting to a single machine, use ssh directly. (only one machine listed after -w argument)
It would be better to log into the machine as your regular user. and then su'ed to root. Changing the root password could lock you out, so it may not be a task to automate. Changing passwords, or editing sshd_conf, or changing rsa/dsa keys, you want to keep your original session open, and try logging in on a second session to test your changes.

As an aside, you might want to look at using cf engine to centrally manage 50 hosts.