Estás cambiando la contraseña de root. sudo quiere su contraseña de usuario.
Para cambiarlo, prueba con passwd , sin argumentos o ejecutándolo a través de sudo .
Alternativamente, puede emitir:
$ sudo passwd <your username>
La contraseña que usa para sudo es la contraseña de su propia cuenta, no la de la cuenta raíz. sudo se usa para otorgarle acceso a los comandos que deben ejecutarse como root sin darle acceso directo a la raíz. Para cambiar su propia contraseña, use passwd sin sudo.