I think Fireworks only supports the RGB colour space - so there will be a colour shift during the CMYK conversion. If you use black text, backgrounds or images the inking will be far beyond 300% and can cause problems (check the 1-2-print FAQ's). Pads suggestions is a good idea, mail them your file and ask if they'll convert it for you.
There was a colour shift with mine from the CMYK conversion (using elements) but they did say that if i e mail them in advance of my next order they'll look to convert it manually to avoid the colour shift. Amazing service considering the price !!
I imagine they'd be happy to do this with designs from other programs.