Está nos repositórios sob totem-gstreamer e totem-common, então você deve ser capaz de fazer isso com:
sudo apt-get remove totem-gstreamer totem-common
Ou entrando em seu gerenciador de pacotes favorito e desmarcando-o lá.
Parece que há um pacote "totem" fictício que instala tudo muito bem, mas por alguma razão na minha instalação do xubuntu ele não foi instalado por padrão, então um sudo apt-get remove totem
apenas retornaria "O totem do pacote não está instalado , então não foi removido "
Editar:
Atualizado o acima para também remover totem-common, o que deixa para trás.