I had a similar problem with my Thinkpad T21.
The solution is simple: It is a bug in the bios.
You'll have to recompile your kernel, and in section "General Setup" you have to enable "Advanced PowAdvanced Power Management BIOS support", and (that's the important one
"Use real mode APM BIOS call to power off".
I also enablede "Enable console blanking using APM", "Enable PM at boot time" and "Make CPU Idle calls when idle", but you don't need them necessarily (even though you might want them whenever working on battery on the console...).