eyoungren:frankly Glenn is much, much more knowledgeable about PDFs and prepress than I am

Erik is too modest, he knows lots that I don't.
frank:They ask for PDF 1.6 and that 1.4 and 1.5 may not work properly. This is from their specs: 1)Aways Embed fonts - if your pdf has text, Always embed the full font family. If at all possible, DO NOT SUBSET FONTS If a font is multiply subsetted in a pdf, when presented to the rip, can produce garbled text. The RIP seems to try to build a single font resource for a multiply subsetted font. But since that font has multiple definitions in the pdf, the font resource that the rip builds can be at the very least garbled from being overwritten over and over again. Furthur, The RIP might reject the font resource entirely, and end up substituting Courier instead. This Usually produces expanded text, reflowing due to expanded kerning. If a pdf file is built from multiple other pdf files, and fonts are subsetted in those individual files, then when they are combined, the final PDF file will have multiply subsetted fonts, which can produce this issue. So, if you fully embed, and never subset, there will be one and only one font definition in your final file.
This is covering themselves.
If A single font is embedded as a subset, multiple times in PDF(1), and the same font is embedded as a subset mutiple times in PDF(2), it is possible for an application to combine these PDFs to make PDF(3) and use only one of the individual subset of that font.
A subset of a font in a pdf is just the characters required rather than the whole megabyte bloaty font.
When an application creates a subset font in a pdf it is supposed to give it a random prefix 8characters long so what is in the PDF looks a bit like ZXCDEGTH-Courier instead of Courier (i forget the correct syntax and it might be a suffix so don't qoute me on this bit) so as long as the 8 characters are different you shouldn't have any problems, thats the theory but if the Application ignores the random bit or it wasn't truly random and you had the same prefix then bam you lose half the characters.
Things to avoid:
Using Acrobat to merge, insert or replace pages, in particular PDFs pages created with Distiller 7 being merged, inserted or replaced in Acrobat 5.
Attempting typos using Acrobat Professional's TouchUp tool.
Placing EPS files with embedded fonts into InDesign 2 or InDesignCS and then Exporting to PDF.
Merging PDFs created in one version of InDesign by placing and Exporting in another.
Using SaveAs or PDFOptimizer in Versions of Acrobat earlier than 9.
If you can fully embed all fonts in all files, rather than subset them all of this can be avoided, unless you PDF Optimize them out, I can't find a setting option in Quark8 (JAWS) that allows you to choose between subset or not, so without Distiller you are a bit stuck.
However this subset replacement is incredibly rare, I've only ever seen it in PDFs produced by mixing InDesign versions. The fact that your printer is aware of it would probably indicate that they won't do anything with your PDF file to cause it.
High end Imposition programs use entirely different routines to combine PDF pages compared to Acrobat or placing them in a DTP app, which is why this shouldn't happen at the printers. Can you ask for an imposed proof?
... there was the puzzle of why the sun came out during the day, instead of at night when the light would come in useful.
Terry Pratchet