If the message above is the shutdown issue, stop right here. You really don't have a problem with shutdown. While it may not seem like it, shutdown has completed properly. The problem you have is with powering down or powering off the computer. Semantics, you say? Maybe, but almost without fail this can be solved as follows. If you haven't checked for an updated BIOS, that's the first step, then check the items listed below.

Click [Start] [Control Panel] [Performance and Maintenance] [Power Options]
The Power Options Properties Property Sheet will open.
Click the APM tab and check the box to [Enable Advanced Power Management Support]

Select the APM tab and check/uncheck [Enable Advanced Power Management Support].

It should be noted that some users have solved the shutdown problems via enabling while others have achieved success via disabling. Experimentation with the APM and ACPI settings may provide a solution.