Eu tive a mesma experiência. Funcionou bem antes de atualizar para o 16.04, mas não depois. Consegui que funcionasse novamente instalando uma versão mais nova do Java JRE e, em seguida, dizendo ao inicializador para usar o novo JRE. Eu instalei o Java JRE da Oracle (você pode obtê-lo em java.com).
Para informar ao pdfsam para usar o novo Java, edite o arquivo em /usr/bin/pdfsam
(talvez seja necessário fazer isso como root). No arquivo da minha máquina, na linha 36, adicionei o seguinte:
JAVA=/home/mike/java/jre1.8.0_101/bin/java
Observe que instalei o Java JRE no meu diretório inicial. Talvez não seja o melhor lugar para fazer isso, mas eu sou a única pessoa que usa essa máquina, então isso funciona bem para mim. Você precisará alterar a linha acima para qualquer local escolhido para instalar o JRE.
O antigo Java JRE ainda está na minha máquina para qualquer programa que ainda precise dele, portanto, isso não deve afetar qualquer outra coisa que você esteja usando no seu computador.
Boa sorte!