It sounds like the standard "transparencies with spot colors" issue in the RIP. Illustrator even warns you about it when you save the document.
Remove your transparencies or remove your spot colors. If you're going to be doing a print-cut with this piece, then you'll have to remove transparencies. You "can" flatten transparencies in Illustrator, but it doesn't look that great and makes the artwork a larger, more complex file.
My personal preference is to open the Illustrator doc with Photoshop and save a JPEG/TIFF out of PS and drop it into Illustrator where the original vectors were and print from this 2nd rasterized doc.
ALSO: a photo of the printed problem helps a TON in diagnosis of your problem.