There is a little room for repeat eigenvalues, as long as we have nontrivial Jordan blocks. For the following, if an integral square matrix commutes with $A_j,$ it is a (rational) polynomial in $A_j$: $$ A_2 \; = \; \left( \begin{array}{rr} 1 & 1 \\\ 0 & 1 \end{array} \right) , $$
$$ A_3 \; = \; \left( \begin{array}{rrr} 1 & 1 & 0 \\\ 0 & 1 & 1 \\\ 0 & 0 & 1 \end{array} \right) , $$
$$ A_4 \; = \; \left( \begin{array}{cccc} 0 & -1 & 1 & 0 \\\ 1 & 0 & 0 & 1 \\\ 0 & 0 & 0 & -1 \\\ 0 & 0 & 1 & 0 \end{array} \right). $$
EDIT : it seems reasonable to conjecture that the full set of $A \in SL_n(\mathbb Z)$ for which the statement is true is $ A \in SL_n(\mathbb Z)$ such that, should there be any eigenvalue(s) of multiplicity larger than one, all occurrences of that eigenvalue must fit into a single Jordan block. Richard would know.
EDIT, 20 November 2011: the conjecture above is true, and does not use integers, it is just about matrices over the complex numbers. This is Corollary 1 to Theorem 2, on page 222 of The theory of matrices, Volume 1 by Feliks Ruvimovich Gantmakher. It reads:
Corollary 1 to Theorem 2: All the matrices that are permutable with $A$ can be expressed as polynomials in $A$ if and only if $n_1=n,$ i.e. if all the elementary divisors of $A$ are coprime in pairs.
SO, the following two conditions, for a square matrix $M$ with real or complex entries, are equivalent:
(I) All matrices that commute with $M$ can be written as a polynomial in $M.$
(II) The characteristic polynomial and the minimal polynomial of $M$ are the same.