Spit, I don't think it's a problem powering down, but rather a problem with powering up after shutting down.
When you shut down does the box go quiet? There is a slight possibility that some kind of virus is showing all outward signs of shutting down whilst actually keeping the PC running. Quite why it would do that I have no idea, and it would be fairly obvious as the fan etc. would probably still run.
Other than that, run spyware/antivirus software. This doesn't sound like a software issue, as the startup obviously happens while there are no programs running. I've seen it where you have to tap the start button twice quickly to get the machine to start, some kind of hardware glitch.