Printing Problem Converting PDF from AI

[Magnum]

I had a brochure project that contained a panel that uses an all black background with a cut out white text and a logo graphic.  Once I export it into a PDF as a high quality print compression option, the black distorts to a faded gray.  The PDF on the screen still maintains the crisp black color but once you output it on a printer, the gray is very obvious.  I thought it was just a printer problem but when I outputted in various printers (Epson, HP, and even the Kinkos laser) the same faded tone came out.

Now I'm forced to export PDFs everything through Photoshop RGB (yah, the printer back rooms laugh at my amateurish practice of submitting stuff that's not CMYK).

Anyone else have this problem?  Is there a better way to approach it?