I checked for this solution around the web, and it looks like the ownership and permissions are already correct:
$ ls -la /sbin/unix_chkpwd
-rwxr-sr-x 1 root shadow 30400 2009-09-04 10:26 /sbin/unix_chkpwd
$ stat -c %a /sbin/unix_chkpwd
I should note that I'm using only a single login on this machine, and still this bug is not completely reproducible.