Solution:
We shall prove that the desired numbers have one of the forms $9k \pm 1$, $3^{3}(9k \pm 1)$ or $3^{6}(9k \pm 1)$.

Suppose that $3$ does not divide $a$. Since $n^{3} \equiv 0, \pm 1 \pmod{9}$, then $a \equiv \pm 1 \pmod{9}$.

Conversely, let $a \equiv \pm 1 \pmod{9}$. Since $9$ divides $1^{3}-1$ and $2^{3}+1$, then there is $n_{0}$ such that $n_{0}^{3}+a=3^{s} t$, where $s \geq 2$ and $t$ is not divisible by $3$. We shall prove that if $n_{1}=n_{0}+2 \cdot 3^{s-1} t$, then $3^{s+1}$ divides $n_{1}^{3}+a$. We have that
$$\left(n_{0}+2 \cdot 3^{s-1} t\right)^{3}+a=3^{s} t\left(2 n_{0}^{2}+1\right)+4 n_{0} 3^{2s-1} t^{2}+8 \cdot 3^{3s-3} t^{3}$$
Since $3$ does not divide $n_{0}$, then $2 n_{0}^{2}+1$ is divisible by $3$. Moreover, $2s-1 \geq s+1$ and $3s-3 \geq s+1$. Hence $n_{1}^{3}+a$ is divisible by $3^{s+1}$ but $3$ does not divide $n_{1}$. Repeating the same argument, we get a positive integer $n_{p}$ such that $3^{2003}$ divides $n_{p}^{3}+a$.

Let now $3$ divides $a<2003$. Then $a=3^{s} b$, where $s \leq 6$. Hence $n$ is divisible by $3$, i.e., $n=3^{p} n_{0}$, where $p \geq 1$ and $3$ does not divide $n_{0}$. If $p \geq 3$, then $3^{9}$ divides $n^{3}$ and does not divide $a$ which implies that $3^{2003}$ does not divide $n^{3}+a$. Hence $p=1$ or $p=2$ and it is easy to see that $s=3$ or $s=6$, respectively.

In the first case we get that $3^{2000}$ divides $n_{0}^{3}+b$, where $3$ does not divide $b$ and $27b<2003$. It follows as above that $b \equiv \pm 1 \pmod{9}$.

In the second case we get similarly that $3^{1997}$ divides $n_{0}^{3}+b$, where $729b<2003$ and $b \equiv \pm 1 \pmod{9}$.

The number of the positive integers $b \equiv \pm 1 \pmod{9}$ such that $b<2003$, $27b<2003$ or $729b<2003$ equals $2 \cdot 222+1=445$, $2 \cdot 8+1=17$ or $1$, respectively. Hence the desired number is equal to $445+17+1=463$.