It seems the shadow utils RPM does not replace the passwd
command. When you install the shadow utils and run pwconv,
you cannot change passwords with passwd anymore and get
passwd: Critical Error. I solved the problem by getting the
current Shadow suite and installing it, which included the
shadow passwd program.
Unable to reproduce this problem. Since Red Hat Linux uses PAM, it
bypasses the shadow utilities in updating the password database. When
you replaced the shadow utilities, you wiped out the PAM authenication
on login and other things.