As Erik says, have a look at the negs closely (with a magnifier if one is handy)...if it's physical damage, like a scratch, it could be grit in the camera, or (more likely) careless handling at the lab. FWIW, I've never been totally satisified with cheapy develop-and-scan packages for either negatives or transparencies. Scanning is like printing, needs care and skill for the best results.
Cheap film is another matter (if it's in date) ....I don't think there are any bad films about, as all own-label color now comes from either Fuji or Kodak (maybe Ferrania?), and none of these companies supply rubbish. Truprint used to be from Agfa (also good), and (I believe) is now Fuji. Even if the film is an "earlier version", it should be fine with good quality processing.