"su - root" or "sudo" complains of incorrect password but normal root login works

If you are unable to sudo or su, there are a couple binaries that may need setuid as the root user. On Fedora, it may just be that the user you're trying to sudo/su with a user who is not in the wheel group (other distributions use the sudoers group instead of wheel).

If you're sure you user is in wheel, check permissions on the sudo and su binaries like this (you should logged in as root for doing so):

ls -l $(which sudo)
ls -al $(which su)

For either, if you see a permission set like this:

---x--x--x 1 root root NNNN  [DATE] /usr/bin/sudo
-rwxr-xr-x 1 root root NNNN [DATE] /bin/su

... your binary does not have the appropriate setuid.

To add setuid to these binaries, do:

chmod u+s /usr/bin/sudo
chmod u+s /bin/su

When you're done, your permission sets should look like this:

---s--x--x 1 root root NNNN  [DATE] /usr/bin/sudo
-rwsr-xr-x 1 root root NNNN [DATE] /bin/su

These binaries need to have setuid (the "s" in the permission set) for non-root users to use them. When you're logged in as non-root user, and you try to su or sudo, the system runs these binaries and checks permissions by looking up passwords, etc. Only the root user has (should have) permission to do those operations, so unless setuid permission bit is on the binaries, the system is running them as your user, which does not have access to those protected password files, etc. That's why the mysterious "su: incorrect password" and "sudo: incorrect password" errors.

Setting setuid set as root on a binary forces the system to run them with temporarily elevated privileges in order to perform the specific (protected) tasks that only the setuid user is allowed to do.

Hope this helps.