Look carefully at the water passages. When I removed the circ pump on my old ford truck with a 302 there was a notch at the bottom of the timing chain cover, it sounds like what you're describing. Even though there's a gasket that goes over that spot, it's supposed to be there and under normal operation, water/coolant should not be in the area above that notch, if that makes sense. I thought it was weird too but that area behind the pump should be dry, so the little gap isn't a problem, and in fact does what skidim described to you.
Does your new pump look different from the old one?
1989 Bravura - repowered with 2001 PCM 351 GT-40 - 1.23:1 PCM Trans.
1989 comp - sold
1985 comp - sold