Hmm...you might try uninstalling HL and then reinstalling it. This will uninstall Blue-Shift as well, but you can always reinstall it. Reboot. Okay, now install HL, and then snag the latest patch. Try playing it and see if you get an error.
Half-Life should run fine on 2000 without any sort of modification, as it does support NT4 out of the box. Win2k was pretty much a more streamlined version of it