Intuitive explanation for the Atiyah-Singer index theorem
I don't think I can really give you the intuition that you seek because I don't think I quite have it yet either. But I think that understanding the relevance of Nigel Higson's comment might help, and I can try to provide some insight. (Full disclosure: most of my understanding of these matters has been heavily influenced by Nigel Higson and John Roe).
My first comment is that the index theorem should be regarded as a statement about K-theory, not as a cohomological formula. Understanding the theorem in this way suppresses many complications (such as the confusing appearance of the Todd class!) and lends itself most readily to generalization. Moreover the K-theory proof of the index theorem parallels the "extrinsic" proof of the Gauss Bonnet theorem, making the result seem a little more natural. The appearance of the Chern character and Todd class are explained in this context by the observations that the Chern character maps K-theory (vector bundles) to cohomology (differential forms) and that the Todd class measures the difference between the Thom isomorphism in K-theory and the Thom isomorphism in cohomology. I unfortunately can't give you any better intuition for the latter statement than what can be obtained by looking at Atiyah and Singer's proof, but in any event my point is that the Todd class arises because we are trying to convert what ought to be a K-theory statement into a cohomological statement, not for a reason that is truly intrinsic to the index theorem.
Before I elaborate on the K-theory proof, I want to comment that there is also a local proof of the index theorem which relies on detailed asymptotic analysis of the heat equation associated to a Dirac operator. This is analogous to certain intrinsic proofs of the Gauss-Bonnet theorem, but according to my understanding the argument doesn't provide the same kind of intuition that the K-theory argument does. The basic strategy of the local argument, as simplified by Getzler, is to invent a symbolic calculus for the Dirac operator which reduces the theorem to a computation with a specific example. This example is a version of the quantum-mechanical harmonic oscillator operator, and a coordinate calculation directly produces the $\hat{A}$ genus (the appropriate "right-hand side" of the index theorem for the Dirac operator). There are some slightly more conceptual versions of this proof, but none that I have seen REALLY explain the geometric meaning of the $\hat{A}$ genus.
So let's look at the K-theory argument. The first step is to observe that the symbol of an elliptic operator gives rise to a class in $K(T^*M)$. If the operator acts on smooth sections of a vector bundle $S$, then its symbol is a map $T^*M \to End(S)$ which is invertible away from the origin; Atiyah's "clutching" construction produces the relevant K-theory class. Second, one constructs an "analytic index" map $K(T^*M) \to \mathbb{Z}$ which sends the symbol class to the index of $D$. The crucial point about the construction of this map is that it is really just a jazzed up version of the basic case where $M = \mathbb{R}^2$, and in that case the analytic index map is the Bott periodicity isomorphism. Third, one constructs a "topological index map" $K(T^*M) \to \mathbb{Z}$ as follows. Choose an embedding $M \to \mathbb{R}^n$ (one must prove later that the choice of embedding doesn't matter) and let $E$ be the normal bundle of the manifold $T^*M$. $E$ is diffeomorphic to a tubular neighborhood $U$ of $T^*M$, so we have a composition
$K(T^* M) \to K(E) \to K(U) \to K(T^*\mathbb{R}^n)$
Here the first map is the Thom isomorphism, the second is induced by the tubular neighborhood diffeomorphism, and the third is induced by inclusion of an open set (i.e. extension of a vector bundle on an open set to a vector bundle on the whole manifold). But K-theory is a homotopy functor, so $K(T^* \mathbb{R}^n) \cong K(\text{point}) = \mathbb{Z}$, and we have obtained our topological index map from $K(T^*M)$ to $\mathbb{Z}$. The last step of the proof is to show that the analytic index map and the topological index map are equal, and here again the basic idea is to invoke Bott periodicity. Note that we expect Bott periodicity to be the relevant tool because it is crucial to the construction of both the analytic and topological index maps - in the topological index map it is hiding in the construction of the Thom isomorphism, which by definition is the product with the Bott element in K-theory.
To recover the cohomological formulation of the index theorem, just apply Chern characters to the composition of K-theory maps which defines the topological index. The K-theory formulation of the index theorem says that if you "plug in" the symbol class then you get out the index, and all squares with K-theory on top and cohomology on the bottom commute except for the "Thom isomorphism square", which introduces the Todd class. So the main challenge is to get an intuitive grasp of the K-theory formulation of the index theorem, and as I hope you can see the main idea is the Bott periodicity theorem.
I hope this helps!
I am going to give a topologically biased answer, which will proceed by restating what the Index Theorem says so that its plausibility (though not its truth) is more immediate. [Oops - I see that Paul Siegel said much of this in the comments following his answer - oh well.]
Philosophy: It is a good thing to take a homology and cohomology theory and find geometric/ analytic models for them as well as the linear and Poincare-Lefshetz duality between them, when the spaces in questions are manifolds.
The most basic example is of course ordinary homology and cohomology, which are quite familiar, but worth revisiting since there are actually a few different models of this philosophy. The standard geometric model for homology is chains, and then cohomology can be obtained as a "formal linear dual." But in an oriented manifold, one can show that differential forms provide functionals on chains and go on to establish the de Rham theorem. Or one can take proper submanifolds as partially-defined cochains and get an intersection-theoretic interpretation of cohomology. Or one can decide that de Rham theory is so wonderful that it should be the basic theory, and then passing to linear duals from there leads to the theory of currents to represent homology.
Another example which works very easily but is not as well known is bordism and cobordism. By definition bordism groups are defined by maps from manifolds. Cobordism is typically defined by maps to Thom spectra, but standard transversality shows that such maps are represented by proper submanifolds. The linear/Poincare/Lefshetz duality between bordism and cobordism is given by intersection theory.
The Index Theorem manifests this philosophy for K-theory. K-theory cohomology classes are of course represented by formal sums (or complexes) of vector bundles. K-homology, as developed in Higson and Roe's book, is represented by Fredholm operators. The pairing between them is roughly "counting the dimensions of spaces of solutions of an operator on a vector bundle." (On some planet with very advanced topologists but relatively weak other flavors of math, one could envision the topologists "inventing" this kind of analysis just so they could have more fun with K-theory.) While the analysis (pseudodifferential operators and the like) which shows that Fredholm operators "pair" with vector bundles is standard enough, showing that there is such a homology theory is of course involved, and takes up much of the Higson-Roe book.
Thus, the Index Theorem follows immediately from the stronger statement that one can define K-homology theory using differential operators and that the pairing between that and K-theory is given by the Index. In order to get the cohomology statement, as Paul Siegel mentions above, one uses the Chern character to translate from K-theory to cohomology but then must multiply by the Todd genus because the Chern character does not preserve Thom classes.
I realize that this stronger statement while perhaps feeling plausible is more of a formal answer than the geometric answer (like for Gauss-Bonnet) that you sought. But when I studied the Index Theorem, mostly on the topological side, years ago I found that this formalism did help me develop some "pictures" for some of the arguments (for example the Fredholm theoretic proof Bott periodicity etc).
By the way, while we're mentioning this philosophy, there is one case which is very much a hot/interesting topic, namely for elliptic cohomology where objects like conformal nets, higher categories and "stringy" topology of manifolds all need to be further developed to tell the story.
This is a very good question and I wish I could give a much better answer. But let me try nevertheless.
My understanding (little as it is) of the index theorem derives from Physics, where -- as I have written elsewhere on MO -- it appears as the Witten index of a supersymmetric theory. When the elliptic operator whose index is under discussion has a geometric origin -- say, mapping between spaces of sections of vector bundles in a compact manifold -- the supersymmetric theory is usually a (possibly, gauged) nonlinear sigma model. A mathematically readable paper on this topic is Luis Alvarez-Gaumé's Supersymmetry and the Atiyah--Singer index theorem to which one should go for the details. But as the OP asks for an "intuitive" explanation, let me continue.
Nonlinear sigma models are theories of harmonic maps $\phi: \Sigma \to X$ between two spaces, where $X$ is the geometrically interesting space in this discussion and $\Sigma$ is some auxiliary space, playing the rôle of the arena where the Physics takes place. The relevant sigma models for index theory are the supersymmetric sigma models, which in addition to the maps $\phi$ also have some other fields $\psi$, which are sections of bundles over $\Sigma$: usually spinors twisted by the pullback by $\phi$ of some bundle on $X$. In the index calculation this would be the difference bundle associated to the elliptic operator. Now, $\phi$ are bosonic fields and $\psi$ are fermionic fields. These names reflect a certain fundamental parity in the space of fields: bosonic and fermionic fields have very different dynamics, but they are related in a supersymmetric theory.
The quantum dynamics of such a supersymmetric sigma model is quite complicated: it is described in terms of path integrals weighted by a complicated interacting action functional; but luckily we are not really interested in doing Physics, but "only" Topology! Since the topological invariant we are after is actually a homotopy invariant, we are free to take a limit in which the path integral can be calculated.
In this limit we can decompose fields into classical configurations and fluctuations and one of the marvelous consequence of supersymmetry is that the bosonic and fermionic fluctuations cancel each other precisely, leaving an integral over a finite dimensional manifold: typically $X$ or $T^*X$, depending on which version of the path integral one uses. Basically in the relevant limit the path integral localises on (locally) constant maps $\phi$. The configuration space for constant maps is $X$ itself, whereas $T^*X$ is the phase space of those configurations. Performing the integral then recovers the index formula.
So, in a nutshell:
$T^*X$ is the phase space of constant bosonic field configurations,
the Todd class is the result of the localised bosonic path integral, and
the Chern character is the result of the localised fermionic path integral.