How to diagnose "sudo: must be setuid root" or "sudo: effective uid is not 0, is sudo installed setuid root?" error ?

Issue

• Getting sudo: must be setuid root error when running sudo as normal user (abc).

/etc/sudoers

abc        ALL=(ALL)       NOPASSWD: ALL

# ls -l /usr/bin/sudo
---s--x--x 2 root root 190904 Mar  4 18:21 /usr/bin/sudo

# stat /usr/bin/sudo
...
Access: (4111/---s--x--x)  Uid: (    0/    root)   Gid: (    0/    root)
...

• Getting sudo: effective uid is not 0, is sudo installed setuid root? error in RHEL 6.