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