Eu encontrei uma solução. Eu instalei o PDF XChange Viewer para Windows (percorrendo o Wine). Tem opção de impressão em formato de livreto que funciona bem.
Outra opção nativa do Ubuntu é instalar o Adobe Reader para Linux. Também possui impressão em formato de livreto. Instale o Acrobate no Ubuntu
EDITAR
Uma opção ainda melhor que acabei de descobrir é um pacote chamado bookletimposer.