"Fresh clean install of W2K on new computer hardware"
1. Latest BIOS and FIRMWARE in new machine? Just because it's new doesn't mean the firmware is current.
2. Microsoft supplies the OS, you get to install all the drivers. Tell about the drivers. Did you check for latest?
3. AMD64 in late April is planned here. A few things to clean up...
Bob
Fresh clean install of W2K on new computer hardware last Tuesday (I had experienced this issue intermittantly prior to upgrade too) New hardware consists of: SATA 120MB HD, AMD64 3000+, Gigabyte MoBo, 512MB PC3200, ATI RADEON 9600xt, Antec TRUE430 PSU.
When I "Shutdown" the computer it will acknowledge my action, as though it will shutdown, but the Desktop stays active and the computer can still be used. Usually on the second attempt I notice icons in the Task tray disappearing and the computer does shut down.
I have seen the GURU's here answer questions here, so i'm sure there is a solution for this.

Chowhound
Comic Vine
GameFAQs
GameSpot
Giant Bomb
TechRepublic