RESPOSTA:
Depois de pesquisar em outros sites, descobri que a versão do Transmageddon disponível no Ubuntu Software Center está desatualizada (v0.25) e a mais recente é a v1.3.
Então eu topei com este site muito útil ( LINK ) e seguiu as instruções sobre como instalar a versão atualizada do Transmageddon.
Aqui está uma captura de tela com o codec xvid: link