Gonna sound silly, but I bet for this printer you needed to save it as RGB.

Printing press (business cards, catalogs, magazines, general publications): CMYK
Photographic printers (1hr photo labs, pro photo labs, anyone "professional" using an inkjet printer): RGB

I worked for one lab where people brought in CMYK documents all the time because "it's the professional format, right?" Printing on actual color photo paper (RA-4) is done with RGB files. The color change you described sounds like that problem - I wish I could remember the exact color outputs that were different to be absolutely certain.

Good luck-
-Lew ;-)