Eu não gostei muito do Medibuntu. Mas usando uma estratégia mais freudiana eu pergunto:
Como foi a instalação do linux desde a origem? Deu problema ou foi tranqüila?
Quando o Amarok diz que não tem determinado codec e pergunta se você quer baixá-lo, quais os passos que você toma?
Você tem esse problema também, com o totem? Como ele se comporta?
Você já tentou iniciar esses programas pelo terminal? Percebeu se surgem mensagens de erro?
Tens como informar as mensagens de erro?
Procure responder todas essas perguntas, quanto mais informação, maior probabilidade de achar a resposta.
Procure executar esses programas através do konsole e coloque todas as mensagens de erro disponíveis.