Consider an arbitrary coloring that satisfies the condition. Divide all the cells on the surface into "frames" as shown in Fig. 2—500 frames around each of the eight vertices (one of the frames is shaded). Then, in the $k$-th frame, counting from the vertex, there are $S_k = 6k - 3$ cells. Since no two colored cells can be adjacent, in this frame there can be at most $\left\lfloor \frac{S_k}{2} \right\rfloor = 3k - 2 = \frac{S_k - 1}{2}$ colored cells. Summing over all 4000 frames and noting that their total area is $6 \cdot 1000^2$, we get that the total number of colored cells does not exceed $\frac{6 \cdot 1000^2 - 4000}{2} = 3 \cdot 10^6 - 2000$.

Fig. 2

Fig. 3

It remains to give an example showing that this many cells can indeed be colored. Call two opposite faces of the cube the top and bottom, and the others the side faces. On each side face, one can mark half the cells in a checkerboard pattern. After this, on the top and bottom faces, one can also color half the cells in all rows except the two extreme ones, leaving those empty—see Fig. 3, which shows two side faces and the top face. It is easy to see that with such coloring, each frame contains the maximum possible number of colored cells. (Instead of checking each frame, one can note that the entire surface is divided into $1 \times 1000$ strips, four of which are empty, and in each of the others exactly half the cells are colored.)

Note. There are other optimal examples. In particular, in the example given, the coloring of the top face can be changed as follows: divide the top face by diagonals into 4 triangles. In each of them, color the cells in a checkerboard pattern (so that the coloring of this triangle matches the coloring of the adjacent side face).