Anyway, it has to convert to RGB when it displays it to you and that's where the colors get weird. You should be able to save it as a TIFF and the printshop should be able to go from there with it. It's just that when you open the cmyk jpeg or w/e with another program it doesn't know how to convert the information to rgb accurately and fucks it up.
That's what I thought first, but it doesn't seem to be that way since the prints also look over-saturated.
Could it be due to the icc profile Photoshop uses (and embedded into the file)? To my knowledge, it (e.g. Picasa) should convert the image to rgb properly (just like it views it properly on Photoshop, and i can convert it to RGB which results in a slight color change)... Am I wrong there? :/
I'm well aware of the fact that CMYK is for printing, which is quite exactly what I'm going to use it for. However, since I have worked on this image in CMYK mode it is supposed to export properly (1:1) if I export a JPEG file.