Why do users lose exchange connectivity when I reboot one of my domain controllers?

Ok,

I've got a 2000 domain controller, and two 2003 domain controllers (one which runs exchange 2003).  Users have windows 2000 professional and outlook 2003.  When I reboot the 2000 domain controller, everyone loses exchange connectivity.  I found these two errors on the exchange servers error log:

this error occurs numerous times all at once:

Event Type:      Error
Event Source:      MSExchangeSA
Event Category:      RFR Interface
Event ID:      9074
Date:            5/6/2005
Time:            9:44:48 AM
User:            N/A
Computer:      EXCHANGE
Description:
The Directory Service Referral interface failed to service a client request. RFRI is returning the error code:[0x3f0].

For more information, click http://www.microsoft.com/contentredirect.asp.


Then, the second error occurs once:

Event Type:      Error
Event Source:      MSExchangeDSAccess
Event Category:      Topology
Event ID:      2103
Date:            5/6/2005
Time:            9:33:46 AM
User:            N/A
Computer:      EXCHANGE
Description:
Process MAD.EXE (PID=1436). All Global Catalog Servers in use are not responding:
scanserv.northerninsuring.com
 

For more information, click http://www.microsoft.com/contentredirect.asp.




The server that is referred to above is the one I rebooted.

The windows 2003 server that does not run exchange (its a file and app server) is the operations master.  I believe that all three domain controllers are global catalog servers so i don't know it says ALL global catalog servers in use are not responding.

I have read the MS articles related to the errors and followed all the steps and found nothing (ran policytest.exe, checked replication,etc etc)

Before I write a book, I'll end here.  Feel free to ask more details about my tcp/ip configs, etc or more on what i've tried.

Thanks

PS-Should I post this in networking instead or as well?