Frequentemente ajudo usuários linux com problemas de codecs multimedia. A sugestão é sempre instalar o W32codes. Mesmo assim, ainda enfrentamos outros problemas como o video tremido, ou o som que não sai e por ai vai.
Como sou um cara focado em solução e não em problemas, quando os codecs estão instalados e mesmo assim exite problemas com execução de videos sugiro a instalação do VLC; é um aplicativo leve e extremamente compatível. Com versão para linux e windows.
Para os usuários de distros base Debian, é possível instalar facilmente pelo apt-get com o comando
| Código: |
apt-get install vlc
|

.
.
.
Os usuários windows devem fazer o download na
página de downloads do vlc
.
.
.

.
.
.
Espero que a dica seja útil.