Neat! It's true for every even $n$ instead of $2004$. Consider the graph $G$ on vertex set $S$ in which two vertices are connected iff they are separated by an even number of lines. We want to prove that $G$ is bipartite, which is the same as showing that it has no odd cycles. Assume now that $x_1,\ldots,x_{2k+1},x_1$ is an odd cycle in $G$. This means that for all $i,\ x_i,x_{i+1}$ are separated by an even number of lines (here $x_{2k+2}=x_1$). Let's check the parity of the number of pairs $(e,\ell)$, where $e$ is an edge $(x_i,x_{i+1})$, and $\ell\in\mathcal L$ separates $x_i,x_{i+1}$. On the one hand, this number is even because by assumption, for each $e=(x_i,x_{i+1})$ there is an even number of $\ell$ which separate $x_i,x_{i+1}$. On the other hand, each line which does not pass through any of the $x_j$ cuts an even number of edges $(x_i,x_{i+1})$, as does each line $x_u,x_v$, and each line which passes through exactly one of the $x_j$ cuts exactly one edge. There's an odd number of such lines, since there's an odd number of $x_j$'s, and for each $x_j$ there is exactly one such line for every point in $S\setminus\{x_i\}$, which has odd cardinality. Adding all of these up, we see that our second count gives an odd number of pairs $(e,\ell)$ as above, contradicting the first count, which said that this number had to be even.

grobber always comes up with so much nice stuff

grobber wrote: Neat! It's true for every even $n$ instead of $2004$. Consider the graph $G$ on vertex set $S$ in which two vertices are connected iff they are separated by an even number of lines. We want to prove that $G$ is bipartite. And so if $p$ and $q$ have the same colour, then the number of lines which separate $p$ from $q$ is odd. But how about "only if"?

Call a pair of vertices good if they have the same color with odd number of lines separating them OR they have different colors with even number of lines separating them. First, color $P_1$ red. Then, color each other $P_i$ red or blue such that $(P_1,P_i)$ is good. Lemma: If $(P,Q)$ and $(P,R)$ are good, then $(Q,R)$ is good. Proof: Let $d(PQ)$ be the number of lines separating $P$ and $Q$, i.e. cutting through segment $\overline{PQ}$. Claim 1: $d(PQ)+d(PR)+d(QR)$ is odd. Proof of Claim 1: Consider two types of lines. Type 1: Line joining two points that are not $P,Q,R$. If it cut through $\triangle PQR$, it must cut at exactly two points. So, in total they cut through $\triangle PQR$ for even times. Type 2: Three lines joining an other point $X$ with $P,Q$, and $R$. If $X$ lies outside $\triangle PQR$, then exactly one of these three lines cut $\triangle PQR$ at exactly one point. If $X$ lies inside $\triangle PQR$, then each of these three lines cut $\triangle PQR$ at exactly one point, so in total at three points. Since there are 2001 other points $X$, in total they cut through $\triangle PQR$ for odd times. Therefore, $d(PQ)+d(PR)+d(QR)$ is odd. Back to the lemma, WLOG $P$ is red. Case 1: $Q$ and $R$ are red --- Then, $d(PQ)$ and $d(PR)$ are odd, so $d(QR)$ is odd, so $(Q,R)$ is good. Case 2: $Q$ and $R$ are blue --- Then, $d(PQ)$ and $d(PR)$ are even, so $d(QR)$ is odd, so $(Q,R)$ is good. Case 3: $Q$ is red, $R$ is blue --- Then, $d(PQ)$ is odd, $d(PR)$ is even, so $d(QR)$ is even, so $(Q,R)$ is good. Case 4: $Q$ is blue, $R$ is red --- Similar to Case 3. From the lemma, it follows that every pair of vertices is good.

Is @grobber's solution really correct? It is not really clear, if the cycle is not geometrically convex, why a line through no points of the cycle $C$ cuts an even number of edges in $C$. And even if the cycle is geometrically convex, it is very possible that a line through a vertex of $C$ does not pass through the geometric interior of $C$ and hence does not separate any edges (contrary to "separating exactly one", as @grobber claims). Nevertheless, an odd cycle solution can be built from @carefully's claim 1 - proving it shows that the graph has no triangle and then if one considers a smallest odd cycle (supposing such exists), by taking an edge $v_1v_2$ and a third vertex $v_3$ not adjacent to $v_1$ or $v_2$ the total number of cutting lines between $v_1$ and $v_2$, $v_2$ and $v_3$, and $v_3$ and $v_1$, must be even by the graph relation, whilst it is odd by @carefully's claim. This gives a contradiction and we are done.