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.