Your file isn't quite truly neutral. As you run your mouse around it in Photoshop, and watch the R, G and B numbers in the Info Panel, you'll see they're not always equal. That's BAD.
However, even though it might partially contribute to a problem like this, it shouldn't make it this bad.
Have you had good black-and-white prints from this lab in the past? If so, do you still have any of them in your possession?