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.