I think SE are totally within their rights to enforce a policy like this without negotiation, although clearly a miscommunication has occurred. I think the people who object to it are imagining a situation with a mythical SJW boogeyperson saying "Don't misgender me! my pronouns are xe/xem/xyr on weekdays and xi/hir/hir after 7 o'clock, unless I feel like a ve/ver/vis in which case you must read my mind and use those."
In reality, I think the likely scenario is more like "I'm a she :)", and unless you continue to use 'he' pronouns then there isn't a problem.
When put this way, it sounds like a much more reasonable policy and I think it would be fair to eject people who object to this from the community (with due process of course).
SE have failed to communicate this properly, and also have failed to react to this crisis in a reasonable way. However, from reading this blog post (which actually goes as far as to quote that "First they came..." poem), and Monica's one, I suspect this is not the root of the problem. Not all beliefs can or should be tolerated, as is touched upon in a quote in Monica's post. That is the purpose of a CoC, to set up a reasonable framework of rules upon which debate and discussion can take place.