Doktor Schliemann
Ma sudo non ti funziona solo con le utilità GTK oppure anche con quelle testuali?
Tipo, se dai "sudo ls" o "sudo cat /etc/issue", tanto per dire due comandi, che succede?
Se non funziona neppure con le utilità testuali, prova ad avviare in "single" mode: aggiungi "single" come parametro del kernel all'avvio, dalla schermata di boot. A quel punto dovresti ritrovarti con un terminale di amministratore. Dai "passwd root" per attivare l'utente root e poi riavvia in modalità normale.
In questo modo, se vuoi lanciare un comando da root, non usi più sudo ma su: puoi provare a reinstallare il pacchetto "sudo".