Illustrator :: Getting Lines Between Colors

I dropped a raster image into Illustrator (AI) and with Live Trace, turned it into a vector image that looks excellent on my monitor. However, when I load the vector file into a PDF and then open the PDF, I see small, light gray hairlines between the colors.
 
I'm making a product label for a client. He wants a particular photograph (JPEG) for the background. The printing house wants vector images in CMYK.I'm fairly new to AI and probably not using "approved methods" although I took what I thought were logic steps to achieve my desired end.
 
I took the RGB JPEG, converted it to a .tiff in CMYK. I also tried converting the JPEG to .bmp and .esp - all in CMYK, before moving to AI. I Also tried placing the JPEG directly into AI.
 
I dropped those images into Illustrator separately and did Live Traces on each. At this stage, each attempt gave me excellent vector images in CMYK, but went wonky when I transfer to PDF.
 
Oddly, when I make a hard copy of that PDF on a hi rez digital printer (2400 dpi), the lines do not appear. However, I am still very concerned about those lines, because I will be sending a job off to be done on four-color offset printing. I'm sure the printer will freak out if he sees those lines and I am even more concerned that those lines may show up in the four-colour print process.
 
A local graphics person I spoke with suggested I would find my solution in Pathfinder, but I tinkered with that feature quite a bit and could not resolve the problem. Although, I wonder yet if that may be where I might find the solution, because when I hit Expand the blue path lines seem to correspond with the troublesome gray lines.
 
Someone else told me to hit Expand and then turn off Stroke. I believe I did that correctly, but there was no difference. I also saw no difference when I applied the maximum value for the Stroke. Other attempts at finding a remedy included Resample deselected, then Resample with a resolution of 300,