This is also a problem when simply installing kdesktop-kde3 over Ubuntu.  In particular, synaptic will try to remove sudo first, but that will fail with warning messages, and then synaptic will abort the entire install.  So, why-ever kde3 is trying to remove sudo, that seems a bug somewhere.

On Kubuntu 10.04 

sudo apt-get install kubuntu-desktop-kde3

[omitting lots of packages installed]

Removing openoffice.org-kde ...
dpkg: sudo: dependency problems, but removing anyway as you requested:
 ubuntu-minimal depends on sudo.
 gksu depends on sudo.
 kdesudo depends on sudo.
 kdelibs4c2a depends on sudo.
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 installed 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)


Is there some workaround?

I thought I had dealt with this before, but I cannot find the bug number.  So, here goes again...

Trinity requires a special version of sudo to operate correctly.  It uses the identical source to the official sudo, but with /opt/kde3/bin and /opt/kde3/games added to the secure path.  If you're a bit security paranoid (like me) and want to make sure I didn't insert any backdoors or the like, just download the source from the PPA and run a diff against the official sudo version--you should only see the secure path change.  There is no way to add items to the secure path except prior to compilation; hence the completely different sudo package.

That being said, here is the workaround:
Before the upgrade/installation of Trinity, open a terminal and:
1. set a root password with:
   sudo passwd
   Be sure to remember the password!
2. Install Trinity through whatever method you find most comfortable
3. Unset (lock) the root password with:
   sudo passwd -l
   This restores the root account to the same state it was in before the password was set and Trinity was installed

Hope this help!