You may want to forget about trying to explain, often in vain, to the customer how to make a PDF from Publisher. MSPUB is a handful, on it's best day. You could just convert the Microsoft Publisher file to Adobe InDesign with Markzware's PUB2ID. (Yes, some touch-up will be needed, but then at least in a source application, not PDF.)
Lately I've been pointing all Pub 2003 and earlier clients towards one of the free PDF print driver solutions like CutePDF and then just fixing things in Acrobat. The PDFs that they produce aren't technically as good as Acrobat Distiller PDFs, but they have the advantage of being free and need almost no setup. By default they will include all fonts and keep graphics at high res (if they are high res in Publisher to begin with). Since you're never going to get a print-ready PDF out of Publisher anyway without some clean up it's not a big deal. For the customer to use it, they just choose the CutePDF printer and print. I'd love it if Adobe would make the Adobe PDF print driver as easy to use.
The 4c blacks are probably caused by RGB black being defined in Publisher. You might be able to get the customer to avoid them by going into Properties of the printer driver they're using and choosing Device Settings, then turning the "Convert Gray Text to Postscript Gray" and "Convert Gray Graphics to Postscript Gray" options to Yes. You have to balance the time it takes to fix the problems with the time it will take to walk the customer thorough changing the settings. Depending on how the original file was setup it's not 100% reliable, so I usually just end up fixing in Pitstop.
Here is the CutePDF homepage <http://www.cutepdf.com/Products/CutePDF/writer.asp>
If you, or they, have Office 2007 then install the Microsoft Save As PDF/XPS plug-in. Save the document as a PDF using the "standard" setting.
Then get a demo copy of Callas pdfColorCovnert (part of Callas pdfToolbox3 Plug-in). Use pdfColorConvert to convert to CMYK. It will grab all the RGB grays/blacks that are vector objects AND RGB gray images and make them separation black and convert all the other RGB objects to CMYK in four clicks of the mouse.