Let's determine the smallest positive integer \( n \), different from 2004, for which there exists an integer-coefficient polynomial \( f(x) \) such that the equation \( f(x) = 2004 \) has at least one, and the equation \( f(x) = n \) has at least 2004 distinct integer solutions.
Let $g(x)$ be a polynomial with the desired property for the number $n$ in the problem. There exists, therefore, an integer $a$ such that $g(a) = 2004$. Let's define the polynomial $g_{1}(x) := g(x + a)$. Clearly, $g_{1}(0) = g(a) = 2004$, meaning that the constant term of $g_{1}(x)$ is 2004. Moreover, the equation $g_{1}(x) = n$ has distinct integer roots $a_{1}, a_{2}, \ldots, a_{2004}$, none of which are 0, since $g_{1}(0) = 2004$. This means that

$$
g_{1}(x) - n = (x - a_{1})(x - a_{2}) \ldots (x - a_{2004}) \cdot g_{2}(x)
$$

where, due to polynomial division, the polynomial $g_{2}(x)$ also has integer coefficients, and let its constant term be $c$. The constant terms of the two polynomials in the equality are equal, so

$$
|2004 - n| = |a_{1}| \cdot |a_{2}| \cdot \ldots \cdot |a_{2004}| \cdot |c|
$$

from which, using that $c \neq 0$, we get that

$$
|2004 - n| \geq |a_{1}| \cdot |a_{2}| \cdot \ldots \cdot |a_{2004}| \geq |1| \cdot |-1| \cdot |2| \cdot |-2| \cdot \ldots \cdot |1002| \cdot |-1002|
$$

From this, it is clear that $0 < n < 2004$ is not possible, so from the above inequality, $n \geq (1002!)^2 + 2004$ follows.

Now let the polynomial $g(x)$ be the following:

$$
g(x) := -(x - 1)(x + 1)(x - 2)(x + 2) \ldots (x - 1002)(x + 1002) + (1002!)^2 + 2004
$$

For this polynomial, $g(0) = 2004$ and

$$
g(\pm k) = (1002!)^2 + 2004
$$

for every integer $1 \leq k \leq 1002$, so the answer to the problem is

$$
n = (1002!)^2 + 2004
$$