Ок, поскольку totem-xine это, так сказать, побочная ветка, то в ней и пропишем.

Попробовал, к сожалению в лоб не получилось. Для того, чтобы можно было ставить
libtotem-xine для программ, в которых явно прописано Requires libtotem (я
пользуюсь rhythmbox) я ставлю для libtotem-xine Provides: libtotem-%version.
Если сюда же добавить Conflicts: libtotem, то пакет оказывается конфликтующим
сам с собой (по крайней менре мне выдаётся сообщение: libtotem кофликтует с
libtotem-xine, хотя в системе стоит только libtotem-xine).

Ну что же, тогда стоит сделать так, как стоило сделать с самого начала:
libtotem-xine, libtotem-gstreamer, обе провайдят libtotem и конфликтуют друг с
другом. https://bugzilla.altlinux.org/show_bug.cgi?id=10346

Решение проблемы - в Bug 10346.

(In reply to comment #0)
> Поскольку libtotem и libtotem-xine конфликтуют по файлам, хотя бы в одной из них
> нужно прописать конфликт на другую.

Уже нет.