@Santoro
Can't you check the PSD file you sent? You can import the file in Illustrator if you only have that. Maybe you set a layer to be invisible or something.
Since you already paid for it you might as well let them redo the printjob. They should be able to produce slightly better results. At least comparable to our home printer prints. That light blue ring is never gonna work, but something closer to that background color should be possible. Just show them your proof and tell them that it should look "like that but better" since that was a simple home printer and their printer is of course far superior

@RayB
As I said, that quote is from the FAQ at ClassicArcadeGrafix.
The gamut of CMYK colorspace is way smaller than that of RGB. The printers used for this are not CMYK printers. They use probably more than 4 inks, perhaps wide gamut inks and what not. Their colorspace is much larger than default CMYK.
We can debate this forever since we are both right. You are right that converting to CMYK will prevent unexpected colors. On the other hand, converting to CMYK throws away a huge lot of color info and your print will look far worse than if you let the printshop convert the RGB file to the colorspace they use in their printer (of course assuming their colorspace conversion software is not written by a monkey and/or their operator is not too closely related to a monkey).
So you can basically choose between:
- having predictable results with a CMYK printjob that will almost certainly look dull and crappy
- find a printshop that uses a printer with a color space that better fits your needs where you will not being completely sure how it comes out, but which will look far better than the predictably poor CMYK printjob.
In fact, 2 shops with better printers/operators were already suggested. They will not be able to print all possible RGB colors (hence you can send them your file to have it checked), but the result will certainly look much better than if you convert to CMYK colorspace yourself.