simple advice yet very important and a common mistake:
do not just change your RGB colorspace to CMYK (Image>Mode), you should "Convert To Profile" via the Edit menu.