Answering my own question: I'll rephrase the argument, or at least crucial parts of it, in the language of quantum computing.
The experiment
We start with a qubit prepared in the state $\sqrt\frac23\,|0\rangle + \sqrt\frac13\,|1\rangle$.
Alice (called $\bar{\mathrm F}$ in the paper, with F standing for "friend") measures the qubit in the computational basis. This measurement is supposed to happen in a perfectly insulated lab. I'll model it as the making of a large number of copies of the qubit, $a$ of them to be precise. The state is then
$$\sqrt{\tfrac23}\,|0^a\rangle + \sqrt{\tfrac13}\,|1^a\rangle.$$
$|0^a\rangle$ and $|1^a\rangle$ model, among other things, Alice's memory of the experimental outcome and any beliefs she forms as a consequence of it. Note that I'm assuming that Alice's measurement doesn't cause objective wave function collapse. F&R also make that assumption; see below.
Alice then prepares another qubit in the state $|{+}\rangle = \sqrt\frac12\big(|0\rangle+|1\rangle\big)$ if she measured $0$, or $|1\rangle$ if she measured $1$. She sends that qubit to Bob (called $\mathrm F$ in the paper), who measures it in the computational basis, in a lab that is perfectly insulated from Alice's and the world (aside from a channel used only to send the qubit). The state is then
$$\big( |0^a0^b\rangle + |0^a1^b\rangle + |1^a1^b\rangle \big) / \sqrt3.$$
Next, someone – who is called $\bar{\mathrm W}$ in the paper (W standing for Wigner), but who I'll call "the demon" for reasons that will be clear later – measures Alice's lab in a basis containing $\big\{ |{+}_a\rangle, |{-}_a\rangle \big\}$, where $|{\pm}_a\rangle \triangleq (|0^a\rangle \pm |1^a\rangle)/\sqrt2$, and we postselect on the outcome $|{-}_a\rangle$. Note that $|{\pm}_a\rangle \ne |{\pm}\rangle^{\otimes\,a}$, which is why I didn't use a superscript.
(That isn't actually how F&R describe that measurement. To give you a sense of what I had to wade through, their description of it is $π^{n:00}_{(\bar w,z)=(\overline{\mathrm{ok}},-\frac12)} = \big[(U^{00\rightarrow10}_{R\rightarrow\bar LS})^\dagger |\overline{\mathrm{ok}}\rangle_{\bar L}|{\downarrow}\rangle_S\big] \big[\cdot\big]^\dagger$. As best as I can tell from the accompanying text, this is supposed to be a Heisenberg-picture measurement of the state of Alice's first qubit at an earlier time before she sends the second prepared qubit to Bob. Such measurements are allowed in principle if there is only unitary evolution between the time of the measurement and the time effectively being measured. But that measurement can't be performed with access to Alice's lab only, since her lab is entangled with Bob's. My $\big\{ |{+}_a\rangle, |{-}_a\rangle \big\}$ measurement represents my best guess as to what they mean here, despite not entirely understanding their notation. It leads to a probability of $1/12$ for the halting condition, which is correct according to F&R, and it leads to a paradox like theirs, so it is "close enough" at least.)
The outcome of the demon's measurement is announced publicly, which means it is irreversible and can be modeled as a wavefunction collapse. After the measurement, if the postselection condition holds, the state is
$$|{-}_a0^b\rangle = \big( |0^a0^b\rangle - |1^a0^b\rangle \big)/\sqrt2.$$
Note that this contains a term, $|1^a0^b\rangle$, that wasn't in the state before. This term represents a world in which Alice measures $1$, and therefore prepares Bob's qubit in the state $|1\rangle$, but Bob measures $0$ – a clear contradiction.
This is followed by a measurement of Bob's lab in a basis containing $\big\{ |{+}_b\rangle, |{-}_b\rangle \big\}$, publicly announced and with postselection on $|{-}_b\rangle$. The halting condition I mentioned earlier is that both postselection conditions hold. F&R then spend a long time deriving a contradiction involving a dozen different logical inferences by their four agents, but as far as I can tell this is all unnecessary, since we already found a contradiction that is visible to all agents when the experiment ends, so I won't bother with it.
Three assumptions
F&R say that their no-go result implies that you must abandon at least one of three assumptions, called Q, S, and C. They also say that their no-go theorem is neutral with regard to which assumption must be abandoned, but that doesn't seem to be true at all.
Q is informally the assumption that "the agents can use quantum mechanics". This is a pure thought-experiment; it can't be conducted in the real world because the demon's measurements are physically impossible to perform. F&R assume QM is correct in their analysis. It makes little sense to me to suggest that the agents might need to use a non-quantum theory to model the outcome of an experiment that by construction is correctly modeled by quantum mechanics. But perhaps that's what the title of the paper is meant to imply.
Formally, Q is supposed to be the assumption that you can learn information about the system at an earlier time by Heisenberg-picture measurements. As I said earlier, I don't think the demon's measurements are actually measurements of that kind, so it's not clear the conclusions F&R have their agents draw from Q are really valid (not because QM is wrong, but because they misapplied it).
S is the assumption that measurements have a definite outcome (i.e., there aren't many worlds). F&R's own analysis of the experiment, which is supposed to be definitive, violates S, since they say that the probability of the halting condition is $1/12$, while if Alice and Bob's measurements caused wave function collapse, it would be $1/4$. The inhabitants of the F&R universe can do experiments that show S is false (such as this very experiment), so it makes no sense for them to believe it.
C is the assumption that agents will never reach contradictory conclusions. The experiment above shows, and I'll show more simply below, that C is inconsistent with the existence of a being with the demon's measurement powers.
A simpler experiment
As far as I can tell, this simpler experiment has all of the interesting properties of the F&R experiment.
Alice prepares a qubit in the state $|0\rangle$, then measures it in the computational basis. The resulting state of her lab is $|0^a\rangle$, which includes her reaction to the result, which may be "well, obviously: I just prepared it in that state."
The demon measures Alice's lab in a basis containing $\big\{ |{+}_a\rangle, |{-}_a\rangle \big\}$, which leaves it in one of those states.
The demon then measures the lab in a basis containing $\big\{ |0^a\rangle, |1^a\rangle \big\}$, and if the result is $|0^a\rangle$ (50% chance), repeats both measurements until the lab's state is $|1^a\rangle$. That state includes Alice's reaction to measuring $1$, which may be "wait, that's impossible; is quantum mechanics wrong?"
In place of $|1^a\rangle$, you can use any vector normal to $|0^a\rangle$, or, with minor changes, any vector. The demon can therefore make Alice remember and believe anything at all. So I think F&R's paradox boils down to the observation that it's impossible to be sure of anything when faced with an adversary who can arbitrarily reprogram your brain.
