O serviço provavelmente ainda está presente. Se assim for, estes arquivos estarão no seu sistema:
/etc/mediatomb.conf
/etc/init.d/mediatomb
O software deve ser instalado em:
/etc/mediatomb/
Se ainda estiver presente, remova-o também.
apt-get remove
não removerá tudo; apt-get --purge remove
também remove arquivos de configuração. Mas, manualmente, adicionamos scripts iniciantes que você precisa remover.