The chromogenic films (B+W developed in color chemicals) always end up with a color cast when printed on color paper. It takes a lot of effort to color correct the images to get the prints to look truly black and white. It can be done, but the personnel and the highly automated (dummy-proof) machines at the local drugstore probably aren't going to get you that result.
And yes this is normal and your negatives are fine. It's in the way that the machine reads them when it makes the prints. The machine is completely set up for color printing, and has no idea that the prints from these negatives should actually be B+W.
B
|