Let $\omega$ be a third root of unity, then $\mathbb{Z}[\omega]$ is a PID.

We have $m^3 = n^2 + n + 1 = (n-\omega)(n-\omega^2)$.

$\gcd(n-\omega,n-\omega^2) = \gcd(n-\omega,\omega-\omega^2) \mid (1-\omega)$, and $(1-\omega)$ is the ramified prime lying over $3$ in $\mathbb{Z}[\omega]$, so from unique factorization of $m^3$ we get that either $(n-\omega)$ and $(n-\omega^2)$ are both roots of unity times cubes, or one is a root of unity times $(1-\omega)$ times a cube and the other is a root of unity times $3$ times a cube. In the second case, $m$ is a multiple of $3$, but then $n^2 + n + 1 \equiv 0 \mod 9$, which is impossible.

If $(n-\omega)$ and $(n-\omega^2)$ are cubes, say $a^3$ and $\bar{a}^3$, then their difference $\omega^2-\omega$ is $a^3-\bar{a}^3 = (a-\bar{a})(a^2+a\bar{a}+\bar{a}^2)$. Thus $a-\bar{a}$ is either a root of unity or a root of unity times $(1-\omega)$, and it must be the latter since $a-\bar{a}$ is pure imaginary. Thus $\Im a \le \Im (\omega-\omega^2) = \sqrt{3}$. The same argument applied to $\omega a$ shows that $\Im \omega a \le \sqrt{3}$, and similarly for other roots of unity times $a$, so $a$ is in a hexagon around the origin that is contained in a circle of radius $2$ around the origin, i.e. $|a| \le 2$, so $m = |a|^2 \le 4$. which doesn't give us any solutions.

Finally we have the case that one of $(n-\omega), (n-\omega^2)$ is of the form $\omega a^3$. Then we have $\pm(\omega^2-\omega) = \omega a^3 - \omega^2 \bar{a}^3$. Write $a = x+y\omega$. Then $\omega a^3 - \omega^2 \bar{a}^3 = (\omega-\omega^2)(x^3+y^3-3x^2y)$, so we have $x^3+y^3-3x^2y = \pm 1$, which is a Thue equation. One solution is $x = -1, y = 2$, leading to the solution $n = 18, m = 7$.

Edit: Mathematica claims that the only solutions to $x^3+y^3-3x^2y = 1$ are $(x,y) = (-2, -3), (-1, -1), (-1, 2), (0, 1), (1, 0), (3, 1)$. Mathematica's documentation says it computes an explicit bound on the size of a solution to a Thue equation based on the Baker-Wustholz theorem in order to solve it, and in this case it seems like the bound was small enough.

8more comments