Solved: it was down to laptop-mode-tools, which I installed as part of this post two weeks ago. I uninstalled that package and my laptop is shutting down properly again.
Since today[*], with Debian Wheezy stock kernel (3.2), my Thinkpad SL410 reboots instead of shutting down when it's running on battery. Works fine when on mains power. During shutdown it says 'Will now halt', then reboots.
Similar to what's seen in this thread: http://forums.debian.net/viewtopic.php?f=7&t=86316&start=15, but shutting down X seems to have no effect. Googling seems to yield a lot of hits for thinkpads and ideapads.
Annoying and no idea why.
The support for SL410 under Debian Wheezy has actually gotten worse during the past year -- now 'mute' doesn't work anymore, and from today it doesn't shutdown on issuing e.g. sudo shutdown -h now.Finally, recently the behaviour of the kernel (3.8) has lead to slowdowns on computer with i915 (intel) graphics, which would include a majority of laptops (a fix is on the way though).
Looking at /var/log/apt/history.log my kernel was updated (not a new version, so a bit confused), two days ago. Nothing else looks important enough.
[*] Given that removing laptop-mode-tools solved it, and that I installed that on the 23rd of March, I must've been running my laptop off of mains power for the past two weeks...alternatively, newer kernels fix this (supposed to be due to the combination of laptop-mode-tools and an apci bug in the kernel) since I've been running 3.7.10 for the past two weeks, and only switched back to 3.2 yesterday.