Estou no Ubuntu 16.04 e parece que o suporte de vídeo está corrompido (ou não está disponível) em qualquer visualizador de PDF nos repositórios.
Eu adoraria ser provado errado!
O arquivo de teste está aqui: link
Existe um vídeo na página 23 que deve ser reproduzido.
(Eu estou ciente do pdfpc, que em princípio tem sua própria maneira de incluir e reproduzir vídeos em arquivos pdf, mas eu não poderia nem conseguir que ele abra seu próprio arquivo de exemplo, no Ubuntu 16.04).
E sim, eu tentei instalar o backend phonom vlc para o okular.
Obrigado por qualquer sugestão!
Parece que o exemplo que você está tentando reproduzir não é apenas um vídeo, mas também o Flash. Ele tem um player de vídeo Flash incorporado, que é usado para reproduzir os vídeos no documento de exemplo que você listou.
Não conheço nenhum visualizador de PDF no Linux que suporte a incorporação do Flash (ou de qualquer outro plug-in do navegador). Mesmo o Chromium não suporta o Flash em PDFs.