To prove Cayley-Hamilton theorem, why can't we substitute $A$ for $\lambda$ in $p(\lambda) = \det(\lambda I - A)$? Cayley Hamilton Theorem states that if $A$ is an $n \times n$ matrix over the field $F$ then $p(A) = 0$.
We note that $p(\lambda) = \det(\lambda I - A)$. Hence, why can't we just substitute $\lambda$ with $A$ and directly prove Cayley-Hamilton Theorem by saying that $p(A) = p(\lambda) = \det(\lambda I - A) = \det(AI - A) = 0$?
 A: The original question was: Can i write $\det(I A - A) = 0$ in a meaningful way? Yes, if the first $A$ is consider as a scalar in the ring $F[A]\subset M_n(F)$, and the second one as the matrix representing $A$. And the reason this works is, indeed, that $A$ is an eigenvalue of the matrix $A$. How is this so? Details are below. Note that to make it work we need to work with modules, since the coefficients will be a ring containing $F$. 
We'll start with some easy statements:
Let $k$ be a field, and $(a_{ij})$ an $n\times n$ matrix with elements in $k$ and $\lambda \in k$ so that there exists an element $v \in k^n$, $v$ nonzero, with $(a_{ij}) \cdot v = \lambda \cdot v$. Then $\det( (a_{ij}) - \lambda I ) = 0$. Indeed, the matrix $(a_{ij}) - \lambda I$ is not invertible. 
Same conclusion, if we substitute $k$ with a $k$-vector space $V$, and there exists a nonzero element $v$ in  $V^{ n}$ with $(a_{ij})\cdot v = \lambda \cdot v$. 
More generally: $k$ a commutative ring, $V$ a $k$-module, $(a_{ij})$ a matrix in $M_n(k)$ and 
$\lambda \in k$ and $v$ in $V^n$  so that $(a_{ij})\cdot v = \lambda \cdot v$. Then $\det((a_{ij}) - \lambda I) \cdot v = 0 \in V^n$. Use the adjoint matrix.
Let now $A$ an $n\times n$ matrix. Let $k \colon = F[A]\subset M_n(F)$ the commutative algebra generated by $A$. $F^n$ is a $k$-module. Let $e_1$,$\ldots $, $e_n$ the standard basis of $F^n$. We have 
$$ (a_{ij}) \cdot \left( \begin{array}{c} e_1 \\ \ldots \\ e_n\end{array} \right ) = 
\left( \begin{array}{c} A\cdot e_1 \\ \ldots \\ A \cdot e_n\end{array} \right ) $$
The above equation says: $\left( \begin{array}{c} e_1 \\ \ldots \\ e_n\end{array} \right )$ in $V^n$ eigenvector for the eigenvalue $A$. It follows that 
$$P_A(A) \cdot \left( \begin{array}{c} e_1 \\ \ldots \\ e_n\end{array} \right )= \left( \begin{array}{c} 0 \\ \ldots \\ 0\end{array} \right )$$
and therefore $P_A(A)=0$. 
$\bf{Added}$: Making sense of $\det(AI - A)$:
Consider the example of  @Jim: 
$$A= \left[\begin{array}{cc}1&2\\3&4\end{array} \right]$$
$$\begin{bmatrix} \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} - 1 & -2 \\ -3 & \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} - 4 \end{bmatrix}\ \ \ ?$$
We need to look at scalars as scalar matrices. So we get
$$\begin{bmatrix} \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} - \begin{bmatrix} 1 & 0 \\ 0 & 1\end{bmatrix} & \begin{bmatrix} -2 & 0 \\ 0 & -2\end{bmatrix} \\ \begin{bmatrix} -3 & 0 \\ 0 &-3 \end{bmatrix} & \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} - \begin{bmatrix} 4 & 0 \\ 0 & 4 \end{bmatrix} \end{bmatrix}$$
This $2\times 2$ matrix, with entries in the commutative algebra $F[A]$, has determinant $P_A(A)$, a matrix of the same size as $A$. And it will always the zero matrix.
A: There is another way to see that the proof must be flawed: by finding the interesting consequences this proof technique has. If the proof would be valid, then we would also have the following generalisation:

Faulty Lemma. Suppose that $A$ and $B$ are $n\times n$ matrices. Let $p_A$ be the characteristic polynomial for $A$. If $B - A$ is singular, then $B$ must be a zero of $p_A$.
Faulty proof: We have $p_A(B) = \det(BI - A) = \det(B - A) = 0$.$$\tag*{$\Box$}$$

This has the following amazing consequence:

Faulty Corollary. Every singular matrix is nilpotent.
Faulty proof: Let $B$ be a singular matrix and let $A$ be the zero matrix. Now we have $p_A(\lambda) = \lambda^n$. Furthermore, by the above we have $p_A(B) = 0$, because $B - A$ is singular. Thus, we have $B^n = 0$ and we see that $B$ is nilpotent.$$\tag*{$\Box$}$$

In particular, this proves that we have
$$ \pmatrix{1 & 0 \\ 0 & 0}^2 = \pmatrix{0 & 0 \\ 0 & 0}. $$
This comes to show just how wrong the proof is!
A: Actually, you can do what you want, but you have to be very careful about what you mean when you evaluate a polynomial with matrix coefficients at a matrix. For example, if you have a matrix polynomial with square matrix coefficients $A_j$ such as
$$
               p(\lambda) = A_{0}+\lambda A_{1}+\lambda^{2}A_{2}+\cdots+\lambda^{n}A_{n},
$$
then what do you mean by $p(M)$ where $M$ is a matrix? Do you mean
$$
             p(M) = A_{0}+MA_{1}+M^{2}A_{2}+\cdots+M^{n}A_{n},
$$
or do you mean
$$
               p(M)=A_{0}+A_{1}M+A_{2}M^{2}+A_{3}M^{3}+\cdots+A_{n}M^{n},
$$
or do you mean the average of these two? Or do you mean something even stranger where some powers of $M$ are to the left of a coefficient and some are to the right?
And why is this important? Because if you factor a matrix polynomial into two others, say,
$$
                 p(\lambda)=q(\lambda)r(\lambda),
$$
then it can happen that $p(M)\ne q(M)r(M)$. Whereas the $\lambda$ commute with the matrix coefficients, $M$ and its powers do not necessarily commute with the matrix polynomial coefficients. To see what I mean, suppose
$$
             P_{0}+\lambda P_{1}+\cdots+\lambda^{l}P_{l} \\
    =(Q_{0}+\lambda Q_{1}+\cdots+\lambda^{m}Q_{m})(R_{0}+\lambda R_{1}+\cdots+\lambda^{n}R_{n}).
$$
This has a very specific meaning:
$$
                       P_{0}=Q_{0}R_{0},\\
                    P_{1}=Q_{0}R_{1}+Q_{1}R_{1},\\
                    P_{2}=Q_{0}R_{2}+Q_{1}R_{1}+Q_{2}R_{0},\\
                           \cdots 
$$
But when you substitute a matrix $M$ for $\lambda$, things don't work out any more. First, you have to choose a left-, a right-, or a mixed-evaluation, and you can see that the above relations are not necessarily preserved during evaluation of the polynomial at a matrix:
$$
       P_{0}+P_{1}M+P_{2}M^{2}+\cdots+P_{l}M^{l} \\
   \ne
        (Q_{0}+Q_{1}M+Q_{2}M^{2}+\cdots+Q_{m}M^{m})(R_{0}+R_{1}M+R_{2}M^{2}+\cdots R_{n}M^{n}).
$$
For example, $P_{1}=Q_{0}R_{1}+Q_{1}R_{0}$ is not enough to guarantee
$$
               P_{1}M=Q_{0}R_{1}M+Q_{1}MR_{0}.
$$
So, factorings of matrix polynomials are not generally preserved under evaluation of polynomials at a matrix $M$, regardless of what convention you choose for evaluating those polynomials.
After trying to discourage you, please note that everything works in the case that you are considering. There is an important special case where everything works: If you use evaluation on the right for $p$, $q$ and $r$, and if $Mr(M)=r(M)M$, then you can move all of the powers of $M$ to the far right in $q(M)r(M)$ to obtain the same thing that you would get if you were to evaluate $p(M)$ on the right. (A similar thing holds for left evaluation.) And this condition is automatically satisfied if the right evaluation $r(M)$ is $0$ because $0$ commutes with everything. Hence, the right evaluation of $p$ at $M$ is $0$ if $p=qr$ and if the right evaluation of $r$ at $M$ is $0$.
Proof of Cayley-Hamilton Theorem: So how does this apply in the Cayley-Hamilton Theorem? Suppose $A$ is an $n\times n$ matrix, and let $A_{i,j}$ be the determinant of the matrix obtained by removing the $i-th$ row and $j-th$ column from $A$. The adjunct matrix $A_{\mbox{adj}}=[(-1)^{i+j}A_{j,i}]$ (note the intentional swap of $i$ and $j$) satisfies
$$
                      AA_{\mbox{adj}}=A_{\mbox{adj}}A = \mbox{det}(A)I,
$$
where $\mbox{det}(A)$ is the scalar determinant of $A$ and $I$ is the identity matrix. In particular, 
$$
               (A-\lambda I)(A-\lambda I)_{\mbox{adj}}=(A-\lambda I)_{\mbox{adj}}(A-\lambda I)=
                 \mbox{det}(A-\lambda I)I
$$
The matrix $(A-\lambda I)_{\mbox{adj}}$ consists of cofactors of $A-\lambda I$ and, as such, each entry in this matrix is a polynomial in $\lambda$ of order between $0$ and $n-1$. By collecting like powers,
$$
          (A-\lambda I)_{\mbox{adj}}=Q_{0}+\lambda Q_{1}+\cdots+\lambda^{n-1}Q_{n-1},
$$
where $Q_{j}$ are $n\times n$ coefficient matrices. Therefore, you have
$$
         (Q_{0}+Q_{1}\lambda + \cdots + Q_{n-1}\lambda^{n-1})(A-\lambda I)=(-1)^{n}p(\lambda)I,
$$
where $p(\lambda)=\mbox{det}(\lambda I -A)$ is the characteristic polynomial of $A$. This factoring is preserved by right evaluation at $A$ because the evaluation of $A-\lambda I$ at $\lambda =A$ gives you the $0$ matrix, which commutes with every matrix including $A$. Therefore, the right- and left- evaluations of $p(\lambda)I$ at $\lambda=A$ must give you $0$ (these evaluations are trivially the same as the usual evaluation of a scalar polynomial at a matrix--the coefficients may be thought of as scalar multiples of the identity matirx.) The conclusion is that $p(A)=0$, which is the Cayley-Hamilton Theorem.
Note: the real crux of the matter is that $p(\lambda)I=Q(\lambda)(A-\lambda I)$ so that $A$ is an obvious $0$ of the polynomial on the right and, hence, also of the characteristic polynomial. It is an odd factoring that one obtains where all matrix coefficients of $p(\lambda)I$ are scalar multiples of the identity. So the hard part is found in the explicit adjunct formula for the inverse of a matrix, which is one of several reasons why determinants remain important.
A: If
$$A = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}$$
then $p(\lambda)$ is the determinant of the matrix
$$\lambda I - A = \begin{bmatrix} \lambda - 1 & -2 \\ -3 & \lambda - 4 \end{bmatrix}.$$
Now I plug in $A$ for $\lambda$ and get
$$\begin{bmatrix} \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} - 1 & -2 \\ -3 & \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} - 4 \end{bmatrix}$$
but I don't know what that is, and I certainly don't know how to take its determinant.
So the reason you can't plug into $\det(\lambda I - A)$ is because that expression only makes sense when $\lambda$ is a scalar.  The definition of $p(\lambda)$ isn't really $\det(\lambda I - A)$, the definition of $p(\lambda)$ is that it's the polynomial whose value on any scalar equals the value of $\det(\lambda I - A)$.
On the other hand I could define a function $P(\lambda) = \det(\lambda - A)$ where I'm now allowed to plug in matrices of the same size as $A$, and I certainly would get zero if I plugged in $A$.  But this is a function from matrices to numbers, whereas when I plug matrices into $p(\lambda)$ I get as output matrices.  So it doesn't make sense to say that these are equal, so the fact that $P(A) = 0$ wouldn't seem to imply that $p(A) = 0$ sense $P$ and $p$ aren't the same thing.
A: Remember that there is a difference between $p(x)$ where $x$ is scalar and $p(A)$ where $A$ is a matrix, the next thing you should notice is that if your deduction is true, then $p(A)=0$, the left hand side of this equation is a matrix, while the right hand side is the scalar $0$. 
What Cayley-Hamilton theorem says is that $A$ satisfies its own characteristic polynomial. If you have worked with minimal polynomials before, the proof of this statement is a simple task (given all of the previous work, obviously).
A: There are already several good answers to the question, but I think we can gain additional insight by considering the following closely related question:

Question: If $A\in M_n(R)$, where $M_n(R)$ is the ring of $n\times n$ matrices over the commutative ring $R$, and $p(x)=\det(x I-A)\in R[x]$ is the characteristic polynomial of $A$, why is
$$p(A)=\det(AI-A)=\det(A-A)=\det(0)=0\tag{1}$$
invalid, while on the other hand something like
$$p(0)=\det(0I-A)=\det(-A)=(-1)^n\det(A)\tag{2}$$
is valid?

Syntactically (1) and (2) are very similar, so the answer is not immediately obvious, and we must examine the semantics.
In both (1) and (2) we interpret the notation $p(s)$ to mean the result of substituting an element $s$ for the indeterminate $x$ in the polynomial $p(x)$. To make sense of this, we must recall the universal property of the polynomial ring $R[x]$:

Proposition: If $\varphi:R\to S$ is a ring homomorphism and $s\in S$ commutes with $\varphi(r)$ for every $r\in R$, then there is a unique homomorphism $\psi:R[x]\to S$ extending $\varphi$ with $\psi(x)=s$:
$\require{AMScd}$
\begin{CD}
R @>\subseteq >> R[x]\\
@V \varphi VV @VV \psi V\\
S @= S
\end{CD}
The homomorphism $\psi$ sends the polynomial $f(x)=r_0+r_1x+\cdots+r_kx^k$ to the element
$$\varphi(r_0)+\varphi(r_1)s+\cdots+\varphi(r_k)s^k\tag{3}$$
We call $\psi$ substitution (or evaluation) at $s$ relative to $\varphi$, and we write (3) as $f(s)$ when $\varphi$ is understood. (Note: the commutativity condition for $s$ is required since $x$ commutes with the elements of $R$ in $R[x]$ by construction.)

Back to the question: if $p(x)=c_0+c_1x+\cdots+c_nx^n$ is the characteristic polynomial of $A$, then in (1) we have, by (3),
$$p(A)=c_0I+c_1A+\cdots+c_nA^n\in M_n(R)\tag{4}$$
where in (3) we're using the homomorphism $\varphi:R\to M_n(R)$ given by $r\mapsto rI$, and the substitution is valid (homomorphic) since $A$ commutes with $rI$ for all $r\in R$.
On the other hand in (2) we have
$$p(0)=c_0+c_10+\cdots+c_n0^n\in R\tag{5}$$
where $\varphi$ is taken to be the identity homomorphism on $R$ in (3).
With these meanings clarified, it's evident that (1) is invalid, because the $p(A)$ on the left-hand side is a matrix in $M_n(R)$ by (4), while the $0$ on the right-hand side is a scalar in $R$, as other folks have already pointed out. However, this doesn't fully explain why (1) is invalid.
To see why (1) is invalid, it's helpful to first see why (2) is valid. On the left-hand side of the first equality in (2) we're substituting $0$ after computing a determinant in $R[x]$, as in (5), while on the right-hand side we're substituting $0$ before computing a determinant in $R$. Why do these agree?
Since the determinant is defined by the same formula regardless of the underlying (commutative) ring, it's a natural transformation, so it makes the following diagram commute:
$\require{AMScd}$
\begin{CD}
M_n(R[x]) @>\det_{R[x]} >> R[x]\\
@V M_n(\psi_0) VV @VV \psi_0 V\\
M_n(R) @>> \det_R> R\tag{6}
\end{CD}
In this diagram $\psi_0$ denotes substitution of $0$, and $M_n(\psi_0)$ denotes entrywise substitution of $0$. All the arrows are homomorphisms of the underlying multiplicative monoids of the rings. Starting with the matrix $xI-A$ at the top left and going right and then down, we obtain $p(0)$. Going down and then right, we obtain $\det(0I-A)$ -- crucially because in both $xI$ and $0I$ we're performing scalar multiplication, which is defined entrywise for matrices. So $p(0)=\det(0I-A)$ and (2) is valid.
What happens when we try to adapt this to (1)? Let $\psi_A:R[x]\to R[A]$ denote subsitution of $A$, where $R[A]$ is the (commutative!) subring of $M_n(R)$ generated by $A$ and the scalar matrices $rI$ for $r\in R$. Then the following diagram commutes:
$\require{AMScd}$
\begin{CD}
M_n(R[x]) @>\det_{R[x]} >> R[x]\\
@V M_n(\psi_A) VV @VV \psi_A V\\
M_n(R[A]) @>> \det_{R[A]}> R[A]\tag{7}
\end{CD}
Again starting with the matrix $xI-A$ at the top left of the diagram and going right and then down, we obtain $p(A)$. But going down and then right, we don't obtain $\det(AI-A)$, and there's no way we could.
To see why, note $M_n(R[A])$ consists of matrices of matrices (not to be confused with block matrices). For $B\in M_n(R[x])$, when we substitute $A$ for $x$ in the entries of $B$, we obtain a matrix each entry of which is a matrix in $R[A]$. If $B=(b_{ij}(x))$ where $b_{ij}(x)\in R[x]$ and $\Psi_A=M_n(\psi_A)$, then $\Psi_A(B)=(b_{ij}(A))$. In particular if $A=(a_{ij})$, then
$$\Psi_A(xI-A)=\Psi_A\begin{pmatrix}
x-a_{11}&\cdots&-a_{1n}\\
\vdots&\ddots&\vdots\\
-a_{n1}&\cdots&x-a_{nn}
\end{pmatrix}=\begin{pmatrix}
A-a_{11}I&\cdots&-a_{1n}I\\
\vdots&\ddots&\vdots\\
-a_{n1}I&\cdots&A-a_{nn}I
\end{pmatrix}\tag{8}$$
If we write $\mathbb{I}=\Psi_A(I)$ and $\mathbb{A}=\Psi_A(A)$, then
$$\Psi_A(xI-A)=A\mathbb{I}-\mathbb{A}\tag{9}$$
where $A\mathbb{I}$ denotes scalar multiplication (not matrix multiplication!) of the matrix $\mathbb{I}\in M_n(R[A])$ by the "scalar" (also a matrix) $A\in R[A]$. When we go down and right in the diagram (7), we obtain $\det(A\mathbb{I}-\mathbb{A})$, which is the matrix $p(A)$ in $R[A]$. The Cayley-Hamilton theorem says that this is the zero matrix:
$$p(A)=\det(A\mathbb{I}-\mathbb{A})=0\tag{10}$$
This analysis explains why (1) is invalid: the "substitution" of $A$ for $x$ in (1) to obtain $AI-A$ is semantically incorrect because it conflates scalar multiplication with matrix multiplication. It also provides the alternative (10) involving scalar multiplication which is valid for the same reason (2) is valid, namely that the determinant is a natural transformation.
