passou pelo mesmo ... você precisa de alguma forma atualizar python-poppler para 0.12.1-9
(Acabei de instalar o pacote pdfshuffler e python-poppler da Yakkety no Xenial; note que em geral isso não é recomendado porque dependências podem quebrar seu sistema, mas são pacotes bem isolados e funcionam no meu sistema; se você souber o que você está fazendo e como restaurar dependências quebradas, experimente ...)