I just tried this a few different ways, and they all worked.  kdesudo-kde3 does provide sudo, and the installations proceeded normally.

I tried:
sudo apt-get install sudo-kde3 [worked properly]
sudo aptitude install sudo-kde3 [worked properly]

Can you post the output of the command you were using when you received the error?

Thanks!

Tim

I just realized it does indeed provide it; I just was used to the old synaptic where it displayed them all together instead of having a dropdown. Also, you accidentally wrote kdesudo-kde3 once, which is the GUI frontend.

I'm guessing you manually set a root password.

me@mybox:~$ sudo apt-get install sudo-kde3
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following packages will be REMOVED:
  sudo
The following NEW packages will be installed:
  sudo-kde3
0 upgraded, 1 newly installed, 1 to remove and 0 not upgraded.
Need to get 0B/179kB of archives.
After this operation, 8192B of additional disk space will be used.
Do you want to continue [Y/n]? y
dpkg: sudo: dependency problems, but removing anyway as you request:
 kdelibs4c2a-kde3 depends on sudo.
 ubuntu-minimal depends on sudo.
 gksu depends on sudo.
 kdesudo-kde3 depends on sudo.
 kdesudo depends on sudo.
(Reading database ... 229315 files and directories currently installed.)
Removing sudo ...
You have asked that the sudo package be removed,
but no root password has been set.
Without sudo, you may not be able to gain administrative privileges.

If you would prefer to access the root account with su(1)
or by logging in directly,
you must set a root password with "sudo passwd".

If you have arranged other means to access the root account,
and you are sure this is what you want,
you may bypass this check by setting an environment variable
(export SUDO_FORCE_REMOVE=yes).

Refusing to remove sudo.
dpkg: error processing sudo (--remove):
 subprocess pre-removal script returned error exit status 1
Errors were encountered while processing:
 sudo
E: Sub-process /usr/bin/dpkg returned an error code (1)

Hmm...I'll ask the Kubuntu devs about that one.  I do always run with a root password set, so I didn't know about this bug.  Thank you for bringing it to my attention!

To anyone having this problem:
The regular version of sudo installed by default with Ubuntu does not have the Trinity binary directories included in its hard-coded RPATH, which makes it very hard or impossible to run Trinity applications as root with sudo.  There is a rebuild of sudo (sudo-kde3) that makes no changes other than to add the Trinity binary directories to that RPATH.

To install it, you need to (temporarily) set a root password with:
sudo passwd
Type a password and press enter

Now run:
sudo apt-get install sudo-kde3

Finally, after installation, unset (lock) the root password with:
sudo passwd -l root

*** Bug 199 has been marked as a duplicate of this bug. ***