1) No boot! Nooooo!
I suspect I got bit by bug 858122. The workaround is in comment #22, and works.
But it made me wonder...
See, you can simply rename the symlinks for shutdown, but then the next time a package manager runs "update-rc.d", everything will get hosed again. Looks like each of 5 init.d scripts needs to be patched to show accurate #stop init information, and those patched pushed upstream...if upstream even has the problem.
That's why Comment #22 is a workaround instead of a fix.
2) Very slow boot
According to syslog,
Oct 19 13:54:06 cheesebot-supremo kernel: [ 3.362104] EXT3-fs (sda1): mounted filesystem with ordered data modeSo let's try commenting out the lp driver in /etc/modules
Oct 19 13:54:06 cheesebot-supremo kernel: [ 33.253915] lp: driver loaded but no devices found
I wonder...will CUPS still work after that?
Answer: Turns out to bot be an issue, but another arcane symptom of the same bug.
3) Boot Message "Waiting for Network Configuration"
Not really finding anything on it, seems polluted with #1.
Could there have been an initscripts install failure during an upgrade?
Answer: Turns out to not be an issue, but yet another arcane symptom of the same bug.
The takeaway: A reminder to be methodical attacking bugs. Fix one, test it, and move on.