You can boot into recovery, and change permissions on /usr/bin/sudo to 4755 (setuid root and executable). Note that in the recovery mode's (root) terminal option, you do not need to use sudo. For good measure, change kdesudo permissions as well.
Originally Posted by jktjs
Your sudo should then look like:
I THINK (absolutely not sure) that re-installing the problematic packages should fix permissions. Eg, if sound is giving a problem, consider reinstalling it as
Wed Sep 26 @16:12:31:~$ ll /usr/bin/sudo
-rwsr-xr-x 2 root root 71288 Jun 1 09:23 /usr/bin/sudo
If you have the time, and would like to experiment before re-installing, try installing the kde-desktop meta package
sudo apt-get install --reinstall phonon
Hopefully, you won't have to download anything at all, unless you have run a recent apt-cache clean (purge old apt .deb files from cache).
sudo apt-get install --reinstall kubuntu-desktop
AT YOUR OWN RISK only, sorry about that.