Your problem revolves around the way that Windows 2000 server with Active Directory works. When you install AD, it creates 5 FSMO's (flexible single masters of operations). One of these is the PDC Emulator. This means that any 'down-level' clients will ONLY authenticate to that server. Even though you have a BDC, the downlevel clients are lookng for the 2000 Domain Controller. When you shut it down, no NT4, or Win9x systems will be able to authenticate. Windows 2000 Pro and XP will authenticate okay, but not the others.
Solution(s). 1. keep the 2000 Domain controller up except during maintenance. 2. upgrade all of your clients to windows 2000 pro or xp.
Best of luck.