Es ist in den Repositories unter Totem-Gstreamer und Totem-Common, also sollten Sie es mit:
sudo apt-get remove totem-gstreamer totem-common
Oder gehen Sie in Ihren bevorzugten Paketmanager und deaktivieren Sie ihn dort.
Es sieht so aus, als gäbe es ein Dummy-Paket "Totem", das alles schön installiert, aber aus irgendeinem Grund in meiner xubuntu-Installation wurde es nicht standardmäßig installiert. Daher sudo apt-get remove totem
würde nur "Paket-Totem nicht installiert, also nicht entfernt" zurückgegeben.
Bearbeiten:
Das obige wurde aktualisiert, um auch das Totem-common zu entfernen, das es zurücklässt.