Here are some details, it is not a complete argument, it requires knowing some descriptive set theory (and there may be some typos), but the sketch should give a decent idea.
I'll actually work with $2^\omega/E_0$ (which is another manifestation of Vitali's relation). I learned this from Benjamin Miller, by the way, and it immediately became key for some results Richard Ketchersid and I have been working on. The result itself, that under AD this quotient does not admit a linear ordering, has been known to descriptive set theorists for ages, I am not sure who first noticed it.
Recall that $x\mathrel{E_0}y$, for $x,y\in2^\omega$, iff there is some $n$ such that for all $m\ge n$ we have $x(m)=y(m)$. It suffices to assume that all sets of reals have the Baire property.
Suppose $R$ is a linear ordering of $2^\omega/E_0$. Then the pullback $\hat R$ of $R$ is a quasi-ordering of $2^\omega$. Begin by noticing that $\hat R$ is not meager. Otherwise, $2^\omega$ itself would be meager, being the union of $\hat R$ and $\hat R^{-1}$ (its ``flip'').
Note that the set
{$x \mid${ $y \mid x \mathrel{\hat R} y$} is non-meager }
is itself non-meager, by the Kuratowski-Ulam theorem, so we can fix some $s \in 2^{<\omega}$ such that
{$ x \mid${ $y \mid x \mathrel{\hat R} y $} is co-meager in $N_s$}
is non-meager, where $N_s$ is the basic neighborhood consisting of sequences in $2^\omega$ that begin with $s$.
The key point is that if a set has the Baire property and $E_0$ restricted to that set is smooth (i.e.,there is a Borel reduction to the identity on that set), then the set is actually meager (this follows from the Glimm-Effros dichotomy of Harrington-Kechris-Louveau).
Note that $E_0$ is smooth on the set
{$x\mid$ there are $y$, $z$ such that $x \mathrel{E_0} y \mathrel{E_0} z$, and exactly one of {$y'\mid y' \mathrel{\hat R} y$}, {$z'\mid z \mathrel{\hat R} z'$ } is co-meager in $N_s$}.
This is not hard, but needs a tiny bit of thought. The point is that any $E_0$-class admits a natural ${\mathbb Z}$-ordering, and on the set above we can pick representatives from each class, since we actually have a way of ``assigning an origin'' to this ordering.
It follows that that the set
{ $x \mid$ for all $x' E_0 x$ the set { $y \mid x' R y$ } is co-meager in $N_s$ }
is non-meager.
Now: This set is $E_0$-invariant, and therefore it must actually be co-meager.
But then $\hat R$ itself is co-meager in $N_s \times N_s$. Now let $E$ be the equivalence relation $\hat R\cap \hat R^{-1}$. Then $E$ is also co-meager in $N_s \times N_s$. But then it admits an equivalence class which is co-meager in $N_s$. Since $E$ actually contains $E_0$, we then have that it is co-meager in all of $2^\omega$.
But then $R$ cannot be a linear order, as it cannot distinguish between co-meager many $E_0$-classes.
[As a final remark: One can of course organize the whole thing using Lebesgue measurability rather than the property of Baire, and Fubini's theorem rather than Kuratowski-Ulam. But the argument using the Baire property shows that this is equiconsistent with ZF (by Shelah), while using measurability would in consistency require an inaccessible.]