ffmpegthumbs 4:15.12.3-0ubuntu1 está com bugs e descompacta ffmpegthumbs.so no local errado. Até que o pacote seja corrigido, uma alternativa é vincular os arquivos ao local correto:
sudo ln -s /usr/lib/x86_64-linux-gnu/plugins/* /usr/lib/x86_64-linux-gnu/qt5/plugins/
Isso funciona na minha instalação do Kubuntu 16.04 LTS. A propósito, ffmpegthumbs precisa de kio-extras para funcionar (deve ser instalado no Kubuntu por padrão como uma dependência de kubuntu-desktop ).