My N800 does that, too. I also do what Sachin recommended: unplug the charger, wait for the display to go blank, then press the power button. I've always had to do that, but then again, I rarely turn my N800 off.
i have never experienced this problem so far, but i do remember an n800 review with a similar shut down/power on problem. i think a reflash fixed it.