Solution:

The answer is $n \geq 5$. If $n \leq 4$, consider $n$ parallel lines. There are 6 total colour combinations required, and only $n+1 \leq 5$ total regions, hence the colouring is not possible.

Now, assume $n \geq 5$. Rotate the picture so that no line is horizontal, and orient each line so that the "forward" direction increases the $y$-value. In this way, each line divides the plane into a right and left hand side (with respect to this forward direction). Every region of the plane is on the right hand side of $k$ lines and on the left hand side of $n-k$ lines for some $0 \leq k \leq n$. Furthermore, there is a region for every $k$: let $w$ be large enough so that $w$ is greater than the $y$-value of any intersection point of two lines. Consider the horizontal line $y=w$: a point very far on the left of this line is left of every single line, and as we cross over all lines in the problem, we hit all values of $k$.

Finally, take a region that is on the right hand side of $k$ lines. Colour it $A_{1}$ if $k$ is odd, and $A_{2}$ if it is even. Similarly, colour it $B_{i}$ if $k \equiv i \pmod{3}$. By the previous paragraph, there are regions for at least $k=0,1, \ldots, 5$, whence there is a region coloured $A_{i}$ and $B_{j}$ for all $(i, j)$. Furthermore, two regions that share an edge will be on the right hand side of $k$ and $k+1$ lines for some $k$. By construction, the $A_{i}$ and $B_{i}$ colours of the regions must differ, hence we have proven that the set of lines is colourable.