Eu fui ao Ubuntu Software Center e instalei o Pdfshuffler.
Tente isso. Apenas pressione Ctrl + Alt + T no seu teclado para abrir o Terminal. Quando se abre, execute o (s) comando (s) abaixo:
sudo apt-get update && sudo apt-get upgrade
e tente instalar novamente o USC. Tente também
sudo apt-get install pdfshuffler
E veja se funciona e me avise.