The reason you get the brown tint is that printing inks don't have equal intensity. It takes a higher density of C than M or Y to produce neutral gray. In other words, C=M=Y does not produce gray, but a reddish brown.
CMYK is not a synthetic color space with ideal behavior. It always corresponds to a specific print process, an offset press calibrated to a certain standard, using certain inks on certain paper stock. It's where the rubber hits the tarmac, so to speak.
That's why we have all these different CMYK profiles. You have to pick one, and you have to pick the right one. The printer can tell you which one to use. Image > Mode just gives you whatever you have set as working CMYK in color settings, and chances are that's not the right one. The Photoshop default (US Web Coated SWOP) is not used anywhere outside the Americas.
The simple way to avoid this is to work in RGB, and if you need to desaturate, do it on an RGB copy. Then you can convert to CMYK when you know you have the correct CMYK profile.