Hi Angeleta,
Do those lines only persist in a map service, or do they also display in ArcGIS Desktop when working with your original map document? Trying to determine where the point of failure lies.
Also, are you publishing an optimized (.msd based) or 'classic' (.mxd based) map service?
Thanks,
Randall