I don't think it's worthy of the outrage and crap in this thread, but, and this is coming from a massive Apple fan, I'm against Apple on this one.
What this boils down to is Apple failed to ensure that their batteries, once degraded, still supply enough voltage to actually power on the device. A device shouldn't throttle with a degraded battery - it should just last less time - that's what people expect, and what pretty much every other device does.
The "well would you rather have your phone shut down unexpectedly" argument doesn't work with me - this is a botched fix to an issue that shouldn't have existed in the first place. Ultimately, it's a software fix for a hardware issue, which isn't acceptable in my books.
Is it class-action worthy? Probably not. But I think Apple should at least offer to replace batteries which are unable to supply enough voltage to power the phone on until it shuts down gracefully with ones that can.
Ultimately, if Apple had gotten their battery calculations right, this wouldn't be an issue. The consumer shouldn't have to suffer because of their mess up.