Using $\{\gamma^\mu, \gamma^\nu\} = 2 \eta^{\mu\nu} \mathbf{1}$, it is easy to show that: \begin{align*} \operatorname{tr} \gamma^\mu \gamma^\nu = 4\eta^{\mu\nu} \end{align*} Now, it is also true that $(\gamma^\rho)^4 = \mathbf{1} \ \ \forall \rho \in \{0,1,2,3\}$. Choosing $\rho \neq \mu,\nu$, one can derive: \begin{align*} \operatorname{tr} \gamma^\mu \gamma^\nu &= \operatorname{tr} \gamma^\mu \gamma^\nu \gamma^\rho (\gamma^\rho)^3\\ &= -\operatorname{tr} \gamma^\mu \gamma^\rho \gamma^\nu (\gamma^\rho)^3 \\ &= -\operatorname{tr} \gamma^\mu \gamma^\nu \gamma^\rho (\gamma^\rho)^3 \\ &= -\operatorname{tr} \gamma^\mu \gamma^\nu \\ \implies \operatorname{tr} \gamma^\mu \gamma^\nu &= 0 \end{align*} where in the penultimate step I used the cyclicity of the trace.
For $\mu = \nu$, this is a contradiction. I am sure there is an easy solution to my confusion, I am baffled that I don't see it.