Answer: 750

Solution:

Write $n = a^2 - b^2 = (a - b)(a + b).$ The factors $a - b$ and $a + b$ differ by the even number $2b,$ so they have the same parity. If both are odd, $n$ is odd; if both are even, $4 \mid n.$ Hence no integer $n \equiv 2 \pmod 4$ is a difference of two squares.

Conversely, every odd number $2k + 1$ equals $(k+1)^2 - k^2,$ and every multiple of $4,$ say $4k,$ equals $(k+1)^2 - (k-1)^2$ (with $k - 1 \ge 0$ since $k \ge 1$).

Between $1$ and $1000$ there are $500$ odd numbers and $250$ multiples of $4,$ for a total of $500 + 250 = 750.$