How many ways to pick 3 different numbers from a group such that one is the average of the others?

How many ways can we pick 3 numbers from 1,2,3,...,500 such that one is the average of the other two? Order does not matter.

I reasoned that we can add either two odd numbers, or two even numbers, since we don't get a whole number if they are different parity and we average them. For the even case, we can choose 250 numbers for the first, then 249 of the other even numbers, then the last number we only have one choice. Similar reasoning goes for the odd case. Therefore we have 250*249*2 choices for the 3 numbers.

The actual answer is half the value I got, what is wrong with my reasoning?

Remember that order doesn't matter. According to your reasoning, the order does matter. So your answer is off by a factor of $2! = 2$. Another way to state your answer is: $$2 \cdot \binom{250}{2} = 2 \cdot \dfrac{250!}{2!248!} = 2 \cdot \dfrac{250 \cdot 249 \cdot 248!}{2 \cdot 248!} = 250 \cdot 249$$