How are you creating the PDF, printing out of ArcMap or exporting? Try switching if you can.
If you have Adobe Acrobat, try printing the pdf to a new pdf, and see if that cleans up the file, or if the line is then visible in the new file.
I take it that this is a specific mxd, not every one you produce?
You might check and repair the geometry of the shapefiles, and see if this goes away.
Regards,
Jim