I had this problem when either the cut line wasn't on the very top of the layer order or there was a transparency on top of the cut line. I use Illustrator and save my files as .eps and make sure it's set to postscript 3.
yup, spot color (CutContour) used with transparency (gradient). In this case I open the art (w/o contour) in PS, flatten & save as JPEG, place back in ILL & save a flattened version to print from. Sucks to have to do, but works 100%. never really noticed a quality loss either.