We finally tracked down the issue. For one reason or another there was another device on our network that was acting as a gateway and was using the same IP address as our Zeroshell gateway. We adjusted the configuration of that device and our issues have disappeared.
