This is one of the most misunderstood topics that I have seen repeated references to. The fact that you build a color in a design application using CMYK build values (percentages) does not mean that the printer will output those percentages of CMY and K ink.
In fact, when you print using a Media Profile (using an ICC Profile), the printer will virtually never print ink using the CMYK values specified in the file. When using a color Managed workflow, those CMYK values will be internally converted into LAB color space (this occurs in the RIP), and then a second conversion occues, back to CMYK, using the ink limits, linearization, and ICC Profile information available for the specific combination of printer, ink, media and resolution that the printer is operating at. It is possible to turn off these color transformations, but doing so can and will often times cause other color problems.
The problem that the original poster is referring to is being caused by metamerism. The solution is to use a color setup that uses more black ink and less cyan and yellow ink in creating the black.
Bob