In a nutshell: If your system is kind of older than sarge (as in installation date, updates done in the mean time don't matter), beware of 2.6.23.x or update your grub boot sector, which Debian doesn't do automatically on package installation.
After 22.214.171.124 lasting for more than a month, I decided on wednesday to finally roll 126.96.36.199 out to most systems. Only to be overrun by seven releases in a row (which even kernel.org infrastructure not properly handled). Ok, so it's 188.8.131.52.
Installation of kernel on my test and semi-productive systems went just fine, so I took the opportunity of being in the datacenter for some unrelated matter on a saturday to update two productive boxes. Just to find them not coming up again. The first box, not connected to a KVM switch, but only to a serial console, looked like it simply died at the place where grub usually says "Loading Linux...", while the second box, on a "real" KVM switch, was a little more helpful, saying "No setup signature found" (or something along this wording).
Since there was no internet on site with the boxes down (one being the main router, the second one being the full service DNS resolver), I quickly chose the fall-back kernel and got back in business. Googling revealed that this is an issue connected with old grub and kernel 2.6.23, and indeed, running grub-setup brought both systems back online. Had I done this - as usual - from remote, this would have been an unexpected downtime of at least half an hour.
Since all systems in question have the same version of grub (the one from etch) installed, I proceeded to investigate what has been going wrong here. Finding that grub does not have any maintainer scripts at all, it would have been my responsiblity to update the grub code in the boot sectors to the new version after updating to etch. The package didn't bother doing this, and this is also not documented in README.Debian or NEWS.Debian. As this is a major pitfall for systems that have been installed pre-sarge, and since updating the Distribution does not solve the issue, I filed Bug #451701. I hope that this blog entry saves other people from unexpected downtimes.
Ah, yes, and barfing the error message on an unused console is a bad foul of grub, see #451710