Let $p$ be a prime. Then $a \in (\mathbb{Z}/p\mathbb{Z})^\times$ is a primitive root of unity if and only if the cardinality statement
$$ \large{|} \normalsize \{ (a^n + a^{p-2-n}) \text{ mod } p \mid \ 0 \le n \le \frac{p-3}{2} \} \large{|}\normalsize = \frac{p-1}{2}$$
holds true.
The proposition holds true for $p = 5,13 \text{ and } 19$ and so there is a good chance it is always true.
So I am looking for a counter-example where it doesn't hold.
$p=3$ and $a=1$ doesn't work: the set has $\frac{p-1}{2}=1$ element and $a=1$ is not a primitive root mod $p=3$.
All other cases (for odd $p$) work: Let $p > 3$ be an odd prime and suppose $0 \leq m < n \leq \frac{p-3}{2}$. Then for $a \in (\mathbb{Z}/p\mathbb{Z})^x$, $$a^n + a^{p-2-n} \equiv a^m + a^{p-2-m} \pmod{p}$$ is equivalent to $$(a^{n-m}-1)(a^{m+n+1}-1)\equiv 0 \pmod{p}$$ and $0 < n-m < m+n+1 < p-1$.
If $a$ is primitive, then the order of $a$ is $p-1$, hence none of the factors is zero. Therefore the set has $\frac{p-3}{2}+1$ distinct values.
If $a$ is not primitive and $a\neq 1$, then the order of $a$ is at least 2 and at most $\frac{p-1}{2}$. The values obtained for $m=0$ and $n=ord_p(a)-1$ are the same, so the set has strictly less than $\frac{p-1}{2}$ elements.
If $a=1$, then the set has only one element, less than $\frac{p-1}{2}$ when $p > 3$.