Musisz zainstalować bodajże:

gstreamer0.10-plugins-ugly albo gstreamer0.10-plugins-bad, nie pamiętam bo nie używam już totema.

Totem korzysta z gstreamera w każdym razie.

Tak na marginesie to dziwne, mam Debiana dosłownie od 10 minut, dodałem repozytoria, zainstalowałem mplayera i w32codecs ...