Changing root password does not change sudo password

You're changing root's password. sudo wants your user's password.

To change it, try plain passwd, without arguments or running it through sudo.

Alternately, you can issue:

$ sudo passwd <your username>

The password you use for sudo is the password of your own account, not the root account. sudo is used to grant you access to commands that need to be executed as root without giving you root access directly. To change your own password, use passwd without sudo.