Illustrator Black Prints Brown...

I have an Illustrator document that is all zebra stripes in pure black, but no matter how I try to trick the program, it prints in a dark brown instead. These are the colors as they stand:

H: 344 S: 11 B: 0

R: 0 G: 0 B: 0

#000000

C: 75 M: 68 Y: 67 K: 90

I have tried the following, to end up with the same brown color printed:

C: 100 M: 100 Y: 100 K: 100

and

C: 0 M: 0 Y: 0 K: 100

and

C: 40 M: 0 Y: 0 K: 100

I am printing with an HP Designjet Z2100 Photo printer, 24inch.

Does anyone have an answer to this? I'm getting desperate, customers really don't like brown zebra stripes!

I have tried getting the printer to recalibrate color, and it is able to print a real black. The really strange thing of it is, once we have saved these illustrator files as jpegs (with a black #00000 number), when we open them in Gimp the black has changed. Yet if we put black type on there, the black type will print black, but the black background will not.

We're not testing anything new or unusual with the printer or ink, we've been using it all along. I think there's something getting changed mid-program-change, but I can't figure where it's happening. The reason I tried that cyan coloring was because of a suggestion online, and it was the only one that 'changed' to the new program with a #000000 coloring, yet still printed in dark brown.

Just my 2 cents worth of input. Vincent is right, don't mix RGB and CMYK together.
Also: check preferences...Appearance of Black and make sure it's set to output all blacks accurately (100% Black will stay 100%Black)and NOT rich black.

Illustrator color mode needs to be cmyk.

Since you have probably heavy areas of black (zebra stripes) I would recommend to use these values. c:20, m:20, y: 20, Black: 100, this would help the printer to build up more density on the black. Stay away from 100% in all 4 colors; coverage shouldn't be more than around 340% if you add al the cmyk values up).

Turn color management off in Illustrator, because if not, Ilustrator tries to color mange the file and the printer will do the same. Let only the printer "manage the colors" and not both.

Before you print create a pdf (color setting during the creation of the pdf should be: "leave as is...don't color manage".

Once created check the black in acrobat. If it's different than what you set it to in Illustrator, it's probably the earlier mentioned "Appearance of Black" in the preferences.

One more thing: Don't print to uncoated paper stock, because the fibers suck up the ink and spread creating a muddy mess. Use coated or semi coated paper (aka: silk, -doesn't need to be glossy)because the ink never hits the paper but sits on top of the coating and looks nice and crunchy.
Hope that helps,
Cheers,
Adolf