if i open my RGB files in adobe-photoshop and then convert to CMYK i will get a better result?
I'm not familiar with the software you're using, so I'm not sure what control you have now. But it will at least give you a second option and will give you the tools to control how the cmyk image looks.
Going from RGB to CMYK you will not be able to produce the full range of RGB colors because the CMYK gamut is smaller.
So:
1.) are you doing the "automatic" RGB -> CMYK conversion correctly and not throwing out the baby with the bath water... (check with your press for basic optimal values and then plug these in under edit: color settings in Photoshop or the corresponding area in your application, e.g. us coated vs. uncoated.)
2.) once you've converted to cmyk, now within the more limited confines of the CMYK space, you can manually tweak problematic colors to be more pleasing by manually adjusting the CMYK levels for those colors.
3.) if you can't work within the gamut limits, then it depends on the type of art how to proceed (and budget) Additional colors can be added to increase the overall gamut or spot colors if there are a few specific bright colors that need to be addressed for example... but adding plates (colors) will definitely increase your cost, so before considering this see how pleasing a result you can obtain manually adjusting the cmyk images in step #2.
Now as an added complication, when you say "But the printer now tells me the resulting colour printing will be different to the original, not so 'colourful' because the initial work wasn't done in CMYK format!" there are two things at play. First the major RGB to CMYK conversion where some colors will not reproduce exactly and some tweaking may be required to get a nice pleasing result. Second, the color calibration of the system you're working on. Optimally if you have a color profile / your monitor is profiled you can get the closest match of the cmyk image on screen to what their proof looks like which is what they'll shoot for on press. It wouldn't be bad at the start to make sure you're close; otherwise spend the $ to profile your system if you're a long way off.)