Why does $O(n \log n)$ seem so linear?
Just some general observations.


O(n log n) is only an upper bound. If it's not tight, that's your explanation right there.
A Θ(n log n) running time can have many different components, for instance

$\qquad\displaystyle a \cdot n\log n + b \cdot n \log \log n + c \cdot \sqrt n + d \cdot n + e \cdot \log n + d$

While technically the linearithmic term dominates, if $a$ is small compared to the other coefficients you will have a hard time detecting it.
Measuring wall-clock running time is noisy without end, inparticular because the coefficients mentioned above get skewed by platform details. Try investigating counts, for instance of a dominant operation or block.
Linear regresssion always works. Since the "difference" between $n \log n$ and $n$ is rather small (also considering above point), it's not susprising you'd get a high confidence. Run linearithmic regression and compare!