Domain controllers not redunant

We just noticed when applying patches to our domain controllers (2 Win2003), that when one was down, no athentication was possible on the network. Then, when the other was down, the same thing happened. Only when both are running, is authenticastion possible.

This, of course defeats the purpose of redundant dcs. We are currently investigate a possible DNS problem, but haven’t come up with a solution.

And yes, we’ve checked to make sure each box was running AD, GC and DNS.

Any ideas would be helpful.