My guess is that this is a well known example (to those that know it well).
I thought quite a lot about it. I found a very satisfying solution, but don't see a systematic approach that would be useful for other problems (this may be my lack of experience in computing chromatic numbers).
You can re-formulate the problem in the way that is being suggested as @Andrew Uzzell: take edges on $\lbrace 1,\ldots,n\rbrace$ connecting pairs $(i,j)$ with $i < j$. You're then looking for an edge colouring of this graph, so that at each vertex the set of incoming colours is disjoint from the set of outgoing colours. (If not then it fails to be an edge colouring of the line graph).
Progress at this point relied on a flash of inspiration: if you try to colour using $k$ colours, where $2^k < n$, then there are two vertices that have the same `incoming colour set' (pigeonhole). You can then show this yields a contradiction.
It turns out that the lower bound is sharp: this is exactly the chromatic number of this graph (as seen by a rather beautiful colouring that I won't describe here). I suspect this is a well known example because it has very large chromatic number ($\log_2n$), while the graph itself doesn't even contain any $K_3$'s. Update: I asked a combinatorial colleague, who hadn't met this example before.