How it turned out: The change of DM went far more smoothly than I expected.
I sent the DM an email (BCCd the rest of the group) to let him know that he was facing a confidence/no-confidence vote today. Ambushes are bad form.
Today he admitted that there was one spot he might have done better. He was still fine with the rest.
The vote came down to three choices:
1) Stay the course and see how it played out. This would allow the DM to hear the complaints and possibly improve his style a bit. His "I might have made one mistake" think didn't help that cause.
2) The characters essentially walk out of the adventure. In story, instead of going through a bureaucratically hostile city into an equally hostile land to track down our missing friend, we stay on the ship and ask the captain to drop us at a different port.
3) Unwind the whole thing, turning time back to just before this DM took over. It never happened, it was a dream, a dark prophesy, a bad bit of pork in the evening meal.
One player wanted to roll a dice to determine his vote. We called that an abstention.
One wanted to go with door #2, mainly because he didn't have a copy of his character from before the DM took over.
Three voted for either winding back time or walking out.
The DM voted for the walk-out.
I voted for the rewind.
One player was absent.
And that's all eight of us. A split vote hedging narrowly towards walking out and letting a new DM try.
And, as is so often the case, the big decision was made based on laziness, because one player didn't want to have to remake an old character sheet.
And life goes on. I think the DM saw the writing on the wall, and decided to bow out gracefully because he was going out no matter what,
He's altered his Cleric, dropping the odd deity that hated all others, and that had no historic counterpart in our pseudo-historic game world.