Essa é uma dica bem simples, você só vai precisar do ffmpeg e todas as suas dependências (não vou falar do processo de instalação porque varia de distribuição para distribuição).

Comando:

ffmpeg -i vídeo_original.avi novo_vídeo.wmv

Obs.: Você pode escolher qualquer formato de entrada e de saída, desde que tenha os codecs dos vídeos instalados.

Exemplo:

ffmpeg -i vídeo_original.ogg novo_vídeo.mkv

ou:

ffmpeg -i vídeo_original.wmv novo_vídeo.mp4

Não importa a extensão de entrada, ele converte para qualquer uma.

Esta dica foi testada no Arch Linux com o codec do MKV instalado pela AUR.

Espero ter ajudado. ;)