If $n$ is a positive integer, does $n^3-1$ always have a prime factor that's 1 more than a multiple of 3?

The case $n=1$ is uninteresting, so let $n\gt 1$. We show that $n^2+n+1$ has a prime factor congruent to $1$ modulo $3$, by showing that $4(n^2+n+1)$ has such a prime factor.

Note that $n^2+n+1$ is odd. We first show that $3$ is not the only odd prime that divides $n^2+n+1$. For suppose to the contrary that $(2n+1)^2+3=4\cdot 3^k$ where $k\gt 1$. Then $2n+1$ is divisible by $3$, so $(2n+1)^2+3\equiv 3\pmod{9}$, contradiction.

Now let $p\gt 3$ be a prime divisor of $(2n+1)^2+3$. Then $-3$ is a quadratic residue of $p$. A straightforward quadratic reciprocity argument shows that $p$ cannot be congruent to $2$ modulo $3$.

Remark: By considering $n$ of the form $q!$ for possibly large $q$, we can use the above result to show that there are infinitely many primes of the form $6k+1$.

For $p\equiv 1\pmod 3$, there exist three distinct solutions of $x^3\equiv 1\pmod p$, and if $n$ is congruent modulo $p$ to such $x$ then $n^3-1$ is a multiple of $p$. Heuristically, this solves the problem affirmatively for a fraction $\frac 3p$ of all possible $n$.

Let's make this a bit less hand-wavy: Let $p_1=7, p_2=13, p_3=19,\ldots$ denote the sequence of prime $\equiv 1\pmod 3$. Then of the $M:=p_1p_2\cdots p_m$ residue classes modulo $M$, there are only $(1-\frac3{p_1})(1-\frac3{p_2})\cdots(1-\frac3{p_m})M=(p_1-3)(p_2-3)\cdots(p_m-3)$ residue classes $x$ for which $n\equiv x\pmod M$ does not imply that $n^3-1$ has a prime factor $\in\{p_1,\ldots,p_m\}$. As we let $m\to \infty$, the product $(1-\frac3{p_1})(1-\frac3{p_2})\cdots(1-\frac3{p_m})$ can be shown to tend to $0$. So at least the density of $n$ that do not work must be zero.