Totem non l'ho mai usato ma kaffeine mi funzionava bene. [Info: Praticamente è solo un frontend per il motore di xine].

Per i video devi mettere i codec nella cartella del player. La mia era, se non ricordo male, /usr/lib/codec ma la puoi cambiare o verificare dalle impostazioni di kaffeine (parlo al passato perchè mi è morto il disco di sistema e ne approfitto per aggiornare il pc, quindi per ora non ho sistemi linux funzionati a disposizione).

Io ho sempre usato il pack di codecs disponibili per mPlayer e funzionano. Per la verità i pacchetti più vecchi mi pare supportassero meglio alcuni formati wmv ma non li avevo conservati.

Questo è il pacchetto più recente disponibile.

Qui invece trovi la directory FTP con tutte le versioni più recenti.

Dovrebbe bastare decomprimere il pacchetto e copiare il contenuto nella cartella dei codecs.