It seems several of the effective user bits for root are missing.
Besides the already mentioned /bin/su permission fix (it actually tells you that it needs to have
suid root), this is also required:
chmod 4755 /usr/bin/sudo
chmod 4755 /usr/bin/passwd
If not fixed, the last one otherwise gives a "token manipulaton error" when changing the password
for oneself being a 'normal' user.
I am not familiar with PAM yet, so I can't comment on if with PAM installed one has to do a different
user setup so that these programs are run in an environment with effective userid root without
explicitly setting the suid bit - but for now, these problems I ran into are taken care of.