Here are examples showing that unlike in the previous problem, here it does not suffice to simply use the fact that the harmonic series / the sum of the reciprocals of the primes diverges. In fact for all $s > 1$ there exists a probability measure on $\mathbb{Z}$ such that for all $n \in \mathbb{N}$ there is at least one class $\bmod n$ which has mass

$$\frac{1}{n} + O \left( \frac{1}{n^{1 + \frac{1}{s}}} \right)$$

where the constant depends on $s$ (and the same will be true for other big-Os appearing in this argument). Note that the exponent $1 + \frac{1}{s}$ can get arbitrarily close to $2$. With some more annoying examples I can do very slightly better than the above, but I still can't reach an exponent of $2$. So let me propose the following companion problem, a negative answer to which would also answer your problem in the negative: 

> Does there exist a probability measure on $\mathbb{Z}$ such that for all $n \in \mathbb{N}$ there is at least one class $\bmod n$ which has mass $\frac{1}{n} + O \left( \frac{1}{n^2} \right)$? 

Now for the examples. What we'll actually work with is a probability distribution on $\mathbb{N}$, but this can straightforwardly be converted to a probability distribution on $\mathbb{Z}$ by setting the mass of a nonpositive integer to be $0$. The distribution in question is just the <a href="http://en.wikipedia.org/wiki/Zeta_distribution">zeta distribution</a> which also appears in the other question; that is, if $X$ denotes a random positive integer then we have

$$\mathbb{P}(X = k) = \frac{1}{\zeta(s) k^s}.$$

The zeta distribution has the property that the numbers $\mathbb{P}(X \equiv a \bmod n)$ are monotonically decreasing, where $a \in \{ 0, 1, \dots, n - 1 \}$, and since they sum to $1$ it follows that they begin at a value $\ge \frac{1}{n}$ and end at a value $\le \frac{1}{n}$. We'll try to find a value of $a$ for which $\mathbb{P}(X \equiv a \bmod n)$ is close to $\frac{1}{n}$ as follows. First, we'll bound the differences between the sums

$$\zeta_{a, n}(s) = \sum_{k \equiv a \bmod n} \frac{1}{k^s} = \mathbb{P}(X \equiv a \bmod n) \zeta(s)$$

as follows. We have

$$\zeta_{a, n}(s) - \zeta_{a+1, n}(s) = \sum_{k \equiv a \bmod n} \left( \frac{1}{k^s} - \frac{1}{(k+1)^s} \right).$$

Each term in the sum can be bounded as follows: 

$$\begin{eqnarray*} \frac{1}{k^s} - \frac{1}{(k+1)^s} &=& \frac{1}{k^s} \left( 1 - \left( \frac{k}{k+1} \right)^s \right) \\
 &=& \frac{1}{k^s} \left( 1 - e^{-s \log \frac{k+1}{k}} \right) \\
 &\le& \frac{1}{k^s} \left( s \log \left( 1 + \frac{1}{k} \right) \right) \\
 &\le& \frac{s}{k^{s+1}} \end{eqnarray*}$$

where we use the inequality $e^x \ge 1 + x$ twice, first in the form $1 - e^x \le -x$ and second in the form $\log (1 + x) \le x$. It follows that

$$\zeta_{a, n}(s) - \zeta_{a+1, n}(s) \le \sum_{k \equiv a \bmod n} \frac{s}{k^{s+1}} \le \frac{s}{a^{s+1}} + \sum_{n \mid k} \frac{s}{k^{s+1}} \le \frac{s}{a^{s+1}} + \frac{s}{n^{s+1}} \zeta(s + 1).$$

This bound is monotonically decreasing as a function of $a$, and now our goal is to find out how large we can take $a$ and still guarantee that $\mathbb{P}(a, n) \ge \frac{1}{n}$. Using the very crude lower bound

$$\zeta_{a, n}(s) \ge \frac{1}{a^s}$$

we see that it suffices to require

$$\frac{1}{a^s} \ge \frac{1}{n} \zeta(s) \Leftrightarrow a \le \left( \frac{n}{\zeta(s)} \right)^{ \frac{1}{s} }.$$

For $a \ge \left( \frac{n}{\zeta(s)} \right)^{ \frac{1}{s} }$ it now follows that 

$$\zeta_{a, n}(s) - \zeta_{a+1, n}(s) \le \frac{s \zeta(s)^{ \frac{s + 1}{s}}}{n^{ \frac{s+1}{s} } } + \frac{s}{n^{s+1}} \zeta(s+1) = O \left( \frac{1}{n^{1 + \frac{1}{s}}} \right)$$

and hence that

$$\mathbb{P}(X \equiv a \bmod n) - \mathbb{P}(X \equiv a + 1 \bmod n) = O \left( \frac{1}{n^{1 + \frac{1}{s}}} \right).$$

Hence for $a \ge \left( \frac{n}{\zeta(s)} \right)^{ \frac{1}{s} }$ the sequence $\mathbb{P}(X \equiv a \bmod n)$ begins at a value $\ge \frac{1}{n}$, ends at a value $\le \frac{1}{n}$, while changing by at most the RHS above. It follows that there is some $a$ in this range for which

$$\left| \mathbb{P}(X \equiv a \bmod n) - \frac{1}{n} \right| = O \left( \frac{1}{n^{1 + \frac{1}{s}}} \right)$$

as desired.