This is not a full answer, just the easy implication that if $n=2^{s}-1$ with $s\ge 2$, then, indeed, all overlaps are even.
We will think of our binary representations of length $s$ as written on the circle. We'll look at each digit sequence separately, so we get (starting with the right bit) $$ 1010101\dots101, \\ 01100110011\dots0011, \\ 000111100001111\dots00001111 $$ etc. Let's do elementary Fourier analysis on $\mathbb Z_n$. The $r$-th sequence $(r=0,\dots,s-1)$ has the Fourier coefficients (up to conjugation, which I'm too lazy to write at 11:15PM) $$ F_r(z)=\frac 1n z^{2^r-1}(1+z+z^2+\dots+z^{2^r-1})(1+z^{2^{r+1}}+z^{2\times 2^{r+1}}+\dots +z^{n+1-2^{r+1}}) \\ =\frac 1nz^{2^r-1}\frac{z^{2^r}-1}{z-1}\frac{z^{n+1}-1}{z^{2^{r+1}}-1} =\frac 1nz^{2^r-1}\frac 1{z^{2^r}+1} $$ for $z^n=1, z\ne 1$. $F(1)=\frac{n+1}{2n}$ regardless of $r$.
The cardinality of the intersection of the $r$-th sequence with the shift of itself by $m$ can be written as $$ n\sum_{z:z^n=1}|F_r(z)|^2z^m=n\sum_{z:z^n=1}\frac{z^m}{|z^{2^r}+1|^2} $$ (Plancherel) This looks pretty useless for determining the individual parities but it shows immediately ($z\mapsto z^{2^r}$ is just a rearrangement of the $n$th roots of unity) that the number of overlaps in the $r$-th position for $m$ is the same as the number of overlap in the $0$-th position for $m/2^r$ where the division is understood in the sense of $\mathbb Z_n$. Thus, instead of asking what happens for the individual $m\ne 0$ in all positions, we can ask what happens in the $0$-th position for $m,m/2,\dots, m/2^{s-1}$ ($m=0$ is a trivial case because the self-overlap in each position is $\frac{n+1}2=2^{s-1}$, which is even when $s>1$ and $n=2^1-1=1$ is, indeed, problematic).
Now we forget all high-tech and just keep this conclusion in mind. Of course, once we know it, we can show it in an elementary way too.
If $m\in\{1,\dots,n-1\}$, then we need to count the pairs of odd numbers in $\{1,2,\dots,n\}$ at distance either $m$ or $n-m$. But that is easy: if $m$ is even, they are $\frac{n+1-m}2=2^{s-1}-\frac m2\equiv \frac m2\mod 2$. Otherwise they are $\frac{m+1}2\equiv_2 \frac{m+1}2+2^{s-1}=\frac{m+n}2+1$.
Thus, if we consider the full cycle $m_r=m/2^r$ ($r=0,\dots,r-1$) in $\mathbb Z_n$ using the representatives $m_r\in\{1,\dots,n-1\}$ (some numbers may repeat, that's OK), then the parity of the number of overlaps in the $0$-th position for the shift by $m_r$ is the parity of $m_{r+1}=\frac{m_r}2$ if $m_r$ is even and of $1+m_{r+1}=1+\frac{m_r+n}2$ if $m_r$ is odd. This means that to get the parity of the full sum over the cycle, we should add the number of odd members of the cycle and the number of $+1$ corrections. But these two numbers are the same because the corrections are generated exactly by the odd members of the cycle, so the final result is always even.
This is quite simple and relatively clean. It is the other implication that seems to be a headache. Any bright ideas?