Possible solution:
You've probably solved this by now, but I Googled for what _seems_ to be the same problem I'm having with a CentOS 4.1 install, found your post, and then remembered I'd seen this problem in July on another server. So, I thought I'd post the solution that worked for me here since it seems the same issue, and your posting was first on Google (maybe it will help some other people who end up here).
It appears to be a bug in shadow-utils. CentOS 4.1 installs with shadow-utils-4.0.3-41.1. If you update to shadow-utils-4.0.3-53.RHEL4, the problem goes away. I got shadow-utils-4.0.3-53.RHEL4 from CentOS 4.2, and installed it on my CentOS 4.1 box to solve this. Also, had to install audit-libs-1.0.3-6.EL4.i386.rpm from a dependency in shadow-utils-4.0.3-53.RHEL4 (can get off the CentOS 4.2 mirrors too).
There is a resolved bug listed on the CentOS.org site about this:
http://bugs.centos.org/view.php?id=979
Links to relevant CentOS 4.2 rpm's (I used the UT mirror in Knoxville, TN):
http://sunsite.utk.edu/ftp/pub/linux.../i386/RPMS.os/
Hope this helps.
