Wolfrs,
Nas vezes em que isto me aconteceu, os plugins estavam lá; o problema era que o programa (Kaffeine, no meu caso) apontava para outro diretório, e não para o correto, onde eles estavam. São duas pastas, geralmente. Aquela dos plugins do Real Player (no meu caso, RealPlayerGold10) e a Win32, com os demais plugins. Sinto não informar exatamente os passos para configurar estes detalhes no programa, mas estou sem meu Linux no momento. Se não encontrar, diga qual é o player que utiliza e eu tento procurar por aqui.