Solution:

If $(x, y, z)$ is a positive solution of $4x + 3y + 2z = 2009,$ then $(x - 1, y - 1, z - 1)$ is a nonnegative solution of $4x + 3y + 2z = 2000,$ and conversely, since $4 + 3 + 2 = 9.$ So $m$ equals the number of nonnegative solutions of $4x + 3y + 2z = 2000,$ and $m - n$ counts the nonnegative solutions of that equation in which at least one variable is $0.$

If $x = 0:$ $3y + 2z = 2000$ forces $y$ even, $0 \le y \le 666,$ giving $334$ solutions. If $y = 0:$ $2x + z = 1000$ with $0 \le x \le 500$ gives $501.$ If $z = 0:$ $4x + 3y = 2000$ forces $y \equiv 0 \pmod 4,$ $0 \le y \le 664,$ giving $167.$ The solutions $(0, 0, 1000)$ and $(500, 0, 0)$ are each counted twice, so $$m - n = 334 + 501 + 167 - 2 = 1000.$$

The remainder upon division by $1000$ is $0.$