¿Error después de Sudo-ing "sudo:Must Be Setuid Root"?

En la computadora de un compañero, cada vez que uso un comando sudo, aparece este error:

sudo: must be setuid root

Probé varias cosas mencionadas en Internet, como cambiar los permisos a 4755 desde un CD en vivo, pero incluso este comando desde un CD en vivo

sudo chmod 4755 /media/device/usr/bin/sudo

da el mismo error.

EDITAR: El colega me dijo que ejecutó este comando, Dios sabe por qué :/

sudo chmod -R 777 / o sudo chmod -R 777 No está exactamente seguro.

Respuesta aceptada:

• Reinicie la computadora, elija la consola de recuperación y escriba los siguientes comandos

  chown root:root /usr/bin/sudo

  chmod 4755 /usr/bin/sudo

• Reinicie la máquina.

• También echa un vistazo a este enlace para arreglar sudo roto.