When you say "weird on the black" are you referring to what it looks like when you black ink runs low... a weak black with poor transitions? If so, that sounds like their printer. Otherwise it could be the color profile. I know they ask for CMYK, but just for fun, try an RGB image. After your change the color mode - then change the ICC to Adobe RGB for the widest color gamut. Save as a new copy and send them that bad boy. See how the results compare. Can you be more specific about the image, and perhaps it's printed use? Also what printer or method (dye sub, inkjet, etc.)are they using?