In Evasiveness of Graph Properties and Topological Fixed Point Theorems on page 46 it states that (where $F$ is the associated chain map for any function $f$):
$$Tr_F(H_0(\Delta, F_p)) = 1$$
Because $F$ acts "trivially" on $H_0$.
Later (on the same page) it mentions, as, in this case, $f$ is an automorphism that the matrix $F$ has zeros on the diagnol, and hence, the trace is always zero. So:
$$Tr_F(H_n(\Delta, F_p)) = 0$$ for $n \geq 0$.
The paper then proceeds to give this long complicated series of summation/algebraic manipulations to show that $0$ does not in fact equal $1$. Why is it not already a contradiction to note that the trace is always $1$ (because $F$ acts trivially) and simutanteously $0$ because $f$ being an automorphism implies a zero trace for $H_0$?
You're confusing two different actions of $f$. The reason that $Tr_F(H_n(\Delta, \mathbb{F}_p)) = 0$ for $n>0$ is not that the matrix has zeroes on the diagonal; it's simply that $H_n(\Delta, \mathbb{F}_p)=0$ so you are taking the trace of a $0\times 0$ matrix. This argument only applies for $n>0$, since $H_0(\Delta,\mathbb{F}_p)$ is not trivial.
The matrix which has zeroes on the diagonal is the action of $f$ on $K_n(\Delta,\mathbb{F}_p)$: that is, on the chains, not the homology. This is because we are assuming $f$ fixes no simplices (not because $f$ is an automorphism), and a basis for the chains is given by the simplices. This does not apply to the action of $f$ on homology, and in particular does not tell you that $Tr_F(H_0(\Delta, \mathbb{F}_p))$ should be $0$.