This is what I usually do when I get stuck with some crude dependency problem:
First dump anything that doesnt work:
# COLUMNS=999 dpkg -P $(dpkg -l|grep trinity|awk '{print $2}')
# COLUMNS=999 dpkg -P $(dpkg -l|grep kde|awk '{print $2}')
# COLUMNS=999 dpkg -P $(dpkg -l|grep puseaudio|awk '{print $2}')
Upgrad/update the rest:
# apt-get update
# apt-get upgrade
# apt-get dist-upgrade
Install what did not work:
# apt-get install desktop-base-trinity kde-trinity
your milage may vary ...
Nik