I still don't know exactly why (it also happened with at least one Linux-generated PDF, to my utter bewilderment), but I've finally figured out how to view them correctly without installing Adobe's (extremely) bloated Acrobat Reader on my Macs.
The one solution that worked for me was to use Ghostscript to convert the PDF files back into "raw" PostScript and then double-click on the resulting .ps file to force Preview to re-encode it into PDF format.
To do that, I got Ghostscript from Fink and used the following gs incantation:
$ gs -dNOPAUSE -dBATCH -sDEVICE=pswrite -sOutputFile=out.ps -f in.pdf
This invokes gs to batch render the input file to a PostScript file, which I then double-click to open in Preview.
Packing It Into a Single File
If (like me) you'd rather read through a single file, here's a nice way to join PDF files in a single converted output file:
$ gs -dNOPAUSE -dBATCH -sDEVICE=pswrite -sOutputFile=out.ps -c save pop -f *.pdf
The "save pop" thing is the key here (remember PostScript is stack-based).
There's also the option to use the pdfwrite device like so:
$ gs -dNOPAUSE -dBATCH -sDEVICE=pdfwrite -sOutputFile=out.pdf -f *.pdf
$ psnup -2 out.ps two-up.ps
Extracting Single Pages
My favorite, however, is this one:
gs -sDEVICE=pdfwrite -dNOPAUSE -dQUIET -dBATCH -dFirstPage=m -dLastPage=n -sOutputFile=out.pdf in.pdf
(taken from here)