O video tentou carregar aqui, sem aparecer nenhuma dessas mensagens (eu fechei o site pois tava muito pesado e minha conexão é ruim).
No meu firefox eu tenho instalado o plugin do flash, o plugin do totem que lê arquivos quicktime e wmv, e outro que lê divx.
Instalando algum desses três pacotes, que você encontra no synaptic ou no Adicionar/Remover, o problema se resolve.