first off -- to remove a boot loader you want either install another one in the same place, or run the command "fdisk /mbr" from a DOS win98SE bootdisk (available from bootdisk.com)
Okay...lets try to tackle this.
I repartitioned the drive, thinking surely that would have killed any trace of Debian or Trustix.
Partitioning only gets rid of the partition table, it still leaves all the data intact, but yes, effictively this should have deleted Debian and Trustix. Let's go over what could have happened
--Maybe you didn't delete the partitions right
--Maybe you deleted the wrong partitions
--Did you use a terminal tool such as fdisk or cfdisk, or did you use a GUI offered with College Linux, if you used a GUI, I would assume the GUI is at fault here, use a linux or DOS boot disk and use cfdisk or fdisk to properly delete the partitions.
--I'm not quite sure about what I am going to say and if it could even happen, but it sounds logical. Since repartitioning only redoes the partition table, it is possible if you used the same size partitions that if the college linux install really did nothing because of the errors that you rewrote the same partition table and it just kept all the data because college linux never wrote over it and repartition does not delete the data.
I am going to have to guess that the errors college linux experienced may not have seemed serious but probably were. Burn the CD's again or get more specific with the errors (or just try again, computers are goofy) and if still no luck then Try a distro like SuSE or Fedora or Mandrake, they are all very GUI oriented and spiffy like you say College Linux is.