Errore dopo il sudo "sudo:Must Be Setuid Root"?

Su un computer di un collega, ogni volta che utilizzo un comando sudo, ottengo questo errore:

sudo: must be setuid root

Ho provato varie cose menzionate su Internet, come cambiare i permessi a 4755 da un live cd, ma anche questo comando da un live-cd

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

dà lo stesso errore.

MODIFICA: Il collega mi ha detto di aver eseguito questo comando, dio sa perché :/

sudo chmod -R 777 / o sudo chmod -R 777 Non è esattamente sicuro.

Risposta accettata:

• Riavvia il computer, scegli la console di ripristino e digita i seguenti comandi

  chown root:root /usr/bin/sudo

  chmod 4755 /usr/bin/sudo

• Riavvia la macchina.

• Dai anche un'occhiata a questo link per riparare sudo rotto.