So that is just the terminal applications way of masking your password. When you type sudo passwd root you are first asked for your standard user password. You will not see any anything being typed into the terminal window, but when you hit enter you should be prompted to type a new password for the root account.
I just posted a blog article here with instructions and screenshots to setting a new root password. Let me know if this works for you!