I second what mattbeals said.
I have an idea what is going on, but without a look on a PDF I can't be sure.
If you have PitStop, check the tiff-image in the PDF: I would bet it is a NChannel-image with one separation color, black. And your old Harlequin-RIP does not know how to handle this and produces another black separation instead of merging it into the process black.
But this is just a guess
Can you save as a CMYK-TIFF from Photoshop? That should work, too, if this is indeed the problem.
