I've had some postcards and some tri-fold brochures printed in the past, and I thought they were excellent quality. But no one ever mentioned Quark Express, support files, or fonts of any kind.
You submitted a PShop file for the camera ready design, but probably had them do any of the text needed for the brochure - right? When we submit a brochure with both the text and the images done the way we want them, the printers will usually need a PageMaker (what I use) or Quark file with separate files for each of the type font(s) that you have chosen to use for your text as well as your image files.
I still have a lot to learn about printing, and am grateful for the good information in this thread.