It appears that the recently released Service Pack 4 for Windows 2000 is causing more trouble than it actually fixes things. Do not see this as an attempt to knock SP4 and tell you to not deploy it. This SP has hundreds of important security fixes, so it is important. If you are having issues you might be interested in a Microsoft KB article that lists about 33 possible updates that may be the cause for your problems.
Before SP4 for Windows 2000 was released, extensive testing was performed to make sure that all the included fixes and updates worked correctly. During the time before SP4 was released, during testing, new customer-requested updates were not incorporated into SP4. Instead, Microsoft scheduled the new customer-requested updates into a future service pack for Windows 2000. To provide solutions to customer requests as quickly as possible, these updates were created as post-SP4 versions of hotfixes, and then released to the customers who needed them. These post-SP4 hotfixes are not included in SP4, but may be included in later service packs for Windows 2000. Additionally, during testing of Windows 2000 SP4 before it was released, some new problems were discovered and were incorporated in SP4. These updates and fixes will also be included in later service packs. However, it was not possible to include these updates or fixes in the post-SP4 hotfixes because they had already been distributed to the customers who requested them. With the release of Windows 2000 SP4, the post-SP4 hotfixes have now been re-created to include all necessary improvements and updates. These updated hotfixes are available to customers to upgrade post-SP4 hotfix versions so that they do not lose functionality and have no conflicts when they install SP4 for Windows 2000 or when they install updates on a computer that is running Windows 2000 SP4. These updated hotfix versions are referenced with the same Knowledge Base article numbers that the post-SP4 versions use. View Microsoft KB article W2KNews.com has put together an anecdotal problems list compiled from user problem reports. Quite interesting. You can check that out here.