Looking at the Wikipedia entry for Primitive roots modulo $n$, I noticed that for some $n$, they came in pairs:
When $n=p^k$ or $2p^k$ and $p\equiv1 \mod{4}$, then $r$ is a primitive root iff $n-r$ is.
I found a proof for this when $n=p$, but not in general. (Exercise online)
Also, when $n=3^k$ or $2(3^k)$ and $k>1$, then $r$ is a primitive root iff $n-r-2$ is.
Finally, when $n=7^k$, then $r$ is a primitive root iff $n-r+1$ is.
Of course, there may be more patterns like these, but these are the ones I've noticed, and I'm sure they've been noticed before, so I'm wondering if anyone can point me in the direction of a general proof here.
Answer for the case $n=p^k$ and $p\equiv 1\ (\ mod\ 4\ )$ :
We have $$(p^k-r)^m\equiv r^m\ (\ mod\ p^k\ )$$ for every even number $m$
and
$$(p^k-r)^m\equiv -r^m\ (\ mod\ p^k\ )$$
for every odd $m$. If $r$ has order $\phi(p^k)$ and $n-r$ not (or vice versa), then the order of $r$ or the order of $n-r$ must be odd. Denote this order with $o$. Then, we have $r^o\equiv\ -1\ (\ mod\ p^k)$ or $(n-r)^o\equiv -1\ (\ mod\ p^k)$. So, $r$ or $n-r$ has order $2o$. Because of $4|p^{k-1}(p-1)$ , we can conclude $2o\ne \phi(n)$, so neither $r$ nor $n-r$ is a primitve root.