Attempt:
We work with $A'$, the matrix with entries $a_{ij}\mod 3$. Note that cubing $A'$ still gives $I$ as $I$ is unchanged by considering remainders $\mod 3$. For the rest of the proof, we will not differentiate between $A$ and $A'$. The minimal polynomial of $A$ divides $x^{3} - 1$ so each eigenvalue $\lambda$ of $A$ satisfies $\lambda^{3} = 1$. The trace of $A^3$ is clearly just $n$ as $A^3 = I$.
Next, note that for integers $a_1, ...., a_n$ we have that $(a_1 +... + a_n)^k = a_1^{k} + a_2^{k} ... + a_n^{k}\mod k$.
Now this is where I am stuck. I would like to say that this implies $\operatorname{tr}(A)^3 =\operatorname{tr}(A^3)$, but why is it that $\operatorname{tr}(A^3)$ is the sum of the cubed diagonal entries of $A$? I can only say that $\operatorname{tr}(A^3)$ is the sum of the cubed eigenvalues of $A$, but these eigenvalues need not be integers so the argument fails.
If I am able to prove this, then the result follows since I have $a^3 = a\mod 3$ for all $a$ in $\{0,1,2\}$.
Edit: I can confirm that my proof does work since $\operatorname{tr}(A)^p = \operatorname{tr}(A^p)\mod p$ for prime $p$ as said here https://rjlipton.wordpress.com/2009/08/07/fermats-little-theorem-for-matrices/
But I can't find the proof for this statement itself.
Here's one solution, although I'm not sure if it's the one your instructor had in mind.
We know the minimal polynomial of $A$ must divide $x^3 - 1$. That means the irreducible factors of the characteristic polynomial are $x-1$ and $x^2+x+1$. Therefore we know that the characteristic polynomial $p$ of $A$ must be of the form $$p(x) = (x-1)^a(x^2+x+1)^b,$$ where $a$ and $b$ are integers such that $a+2b = n$. The trace of $A$ is the negative coefficient of $x^{n-1}$. But we have $$(x-1)^a = x^a - ax^{a-1} + O(x^{a-2}),$$ and $$(x^2+x+1)^b = x^{2b} + bx^{2b-1} + O(x^{2b-2}),$$ and therefore we have $$p(x) = x^n + (b-a)x^{n-1} + O(x^{n-2}).$$ It follows that the trace of $A$ is given by $$\mathrm{tr}(A) = a-b.$$ This is equivalent modulo $3$ to $a+2b = n$, as required.