Yes - what KIND of printer is this?

Are they press-printers - magazines, brochures, pamphlets, newsletters? Then yes, they'll need CMYK.

Are they photo-printers - using anything from RA-4 chemical processed papers (minilabs, etc. - printing is done by projected light - whether a lamp or LEDs), inkjets? Then they'll need it to be RGB. If you convert an image to CMYK for THESE printers, it'll come back one giant "bluh..."

Ask what color space they WANT, and give them that - it does sound like you went in the wrong direction based on your description.

I hope this helps-

-Lew