There are a few PDF documents around here, that I can read with Acrobat Reader w/o problems, but xpdf and its companions moan. I guess, that’s because they got modified and a little destroyed using Acrobat X Pro.
I used pdftk to get rid of that problem: first output/uncompress, than output/compress again:
$ pdftk x.pdf output
$ pdftk x.uncompressed.pdf output