Дело даже не в кодеках, я когда то сталкивался с такой же проблемой и для решение этой проблемы поступил следующим образом:
Хоть и пишут при установке дистрибутива, что мол xmms поддерживает проигрывание mp3, все это ерунда, на самом деле версия поставляемая по умолчанию не поддерживает mp3.
Для того чтобы все работало необходимо скачать xmms, это можно сделать пройдя по ссылке: http://www.xmms.org/files/1.2.x/rpm/xmms-1.2.10-1.src.rpm это версия для RedHat подобных систем, так же на http://www.xmms.org/download.php можно скачать исходники xmms.
После того как все будет собрано необходимо запустить программу # alsamixer и выставить значение звука, естественно не 0
Вот и вся проблема.
А для видео прекрастно подходит mplayer, удачи.