What you have here is a light leak from the edge of the camera. It is more or less noticeable depending on how long the time period between shots. The longer the period, the more light gets in, and the more intense the mark.
You do not see it so easily in B&W because it will show up as a light haze.
Replace the seals on your camera. In any case these usually deteriorate after about 10 years anyway.
If it was the lab at fault, a lot more people would be complaining, and professional labs do not make this kind of mistake on a regular basis.
Cheers
Ian