I don't think so, V.
I say this because I looked at his two flattened JPGs, not just his PSD, and I looked at them in numerous file viewers, some of which I know aren't color managed, and it looked jet black in all but one image viewer. The reason it looked different in that one viewer is that it's so ancient, it doesn't even understand that there can be CMYK jpgs -- it thinks every jpg is an RGB jpg, LOL.
So, if there is anything wrong with the blacks in these files, it's something very minor.
I suspect that the OP believes there is something wrong with the file because he sees a problem when he tests it in different ways. However, I suspect that the reason for this is that each of his testing methods is likely faulty. Specifically:
a) He never specified what file viewing software he used to test his image.
b) He sent it to an office printer and got bad results - well, duh, what do you expect if you send a CMYK file to a place used to dealing only with sRGB files.
c) He printed it on a desktop printer and got bad results - Do we know if this printer has ever produced a good print from a CMYK file? Most home desktop printer drivers only expect RGB files not CMYK files.
d) And, he hasn't replied to my question about how many different offset printing companies he had bad luck with. On one end of the spectrum, there are offset printers that produce the dirt cheap fliers that you find under the windshield wipers of your car, and at the other end, there are offset printers that produce National Geographic.
Cheers,
T