Answer: B

Small Hint:

The terms $a_n$ and $a_{n+3}$ always share the same parity; use this with $a_{2006} = 1$

Big Hint:

Every term is a multiple of $\gcd(a_1, a_2),$ so $\gcd(999, a_2) = 1;$ note $999 = 3^3 \cdot 37$

Solution:

The rule gives $a_n \equiv a_{n+3} \pmod 2,$ so $a_2$ has the same parity as $a_{2006} = 1;$ thus $a_2$ is odd.

Every term is a multiple of $\gcd(a_1, a_2),$ and $a_{2006} = 1$ forces $\gcd(999, a_2) = 1.$ Since $999 = 3^3 \cdot 37,$ we need $a_2$ not divisible by $3$ or $37.$

Among the odd integers in $[1, 998]$ there are $499;$ removing the $166$ multiples of $3$ and $13$ multiples of $37,$ then adding back the $4$ multiples of $111,$ leaves $$499 - 166 - 13 + 4 = 324.$$

Each such $a_2$ works. For consecutive positive terms $u,v,$ the update $(u,v)\mapsto(v,|v-u|)$ reduces their maximum within at most two steps. Since both initial terms are at most $999,$ some $a_N=0$ occurs by $N\le1999.$

The gcd of each consecutive pair is invariant, so the equal terms immediately before that zero both equal $\gcd(999,a_2)=1.$ The sequence then cycles through $1,1,0.$ Finally, $2006\equiv2\pmod3,$ so $a_{2006}$ has the same odd parity as $a_2;$ in this cycle it must therefore be $1.$

Thus, the correct answer is B.