The current release of pdfshuffler needs python-poppler [1] as a replacement for ghostscript to run. At the moment python-poppler is not in Fedora. [1] https://launchpad.net/poppler-python
This bug appears to have been reported against 'rawhide' during the Fedora 11 development cycle. Changing version to '11'. More information and reason for this action is here: http://fedoraproject.org/wiki/BugZappers/HouseKeeping