The conversion from RGB to CMYK is being done wrong.
To understand that, try to understand this.
RGB is a 3 color space and cmyk is 4. While there are similarities
between R and C, G and M, and B and Y, there is nothing to account for K.
When a specific RGB color is converted to cmyk there are a huge numbver
of possible combinations, each depending on the amount of K that is
"extracted" from the RGB colors.
For instance, RGB 128,128,128 is a medium grey. That's what it would
look like on your screen and probabely your desktop inkjet (if not,
there's a calibratipon problem).
This can be represented in CMYK as 0,0,0,50 or as 56,48,48,0 or as 30,26,
26,20 or many other combinations. Each of these will come off press as a
medium grey, all about the same (slight differences would be attributed
to inconsistencies on press, in the inks, etc).
When a color image is converted to cmyk the process needs to know how
the black it to be handled. In Photoshop, for example, certain default
assumptions are made that (IMHO) by default produce too strong a black
and result in too dark and image. One can see this (in Photoshop, not MS
Publisher) by looking at just the K channel of plate. The black should
have very little detail and be almost a ghosted image not a full
strength back that would stand in for a regular B&W halftone. to resolve
the issue in Photoshop one needs to set a custom conversion.
So what has possibly happened to your images is that the conversion to
cmyk made too strong a K channel. Conversions are usually handled by
color profiles and choosing the wrong or inappriopriate profile results
in a wrong conversion. There is nothing you can do about this, it is the
result of the way they have their conversion set up. and far (far far!)
too many small shops (even some larger ones) simply do not understand
the issues in rgb>cmyk conversion.
Of course, it is also entirely posissible that your RGB images really
are too dark and that you simply don't realize it. A very large
percentage of the RGB images I get are too dark themselves and will
convert to even darker cmyk regardless of cponversion procedure/profile.
Plus 600 dpi is far too much and cannot help.