Logon takes excessive amount of time

When switching on workstations on a Windows 2000 server domain it takes an excessive amount of time for the logon box to appear. Once it eventually appears it again takes an excessive amount of time to logon (sometimes can take upto 30 mins). This has just started happening. Nothing I know of has been introduced. If during the workstations bootup process I remove the network connection the workstations the boot process and logon process is a lot more rapid (normal).
Any idea why this is happening all of a sudden and what checks I can perform to help identify the problem?