The use of complex numbers is never really essential, but if applicable it is almost always more convenient than the equivalent representation in a 2d real vector space (in fact, one typically learns the formal properties of complex number manipulations by their effect on $(a,b) = a+ib.$)
You mention that complex numbers don't seem necessary for classical electrodynamics, and I agree -- however I can't imagine any clear-minded person forgoing their use. In fact it is in classical E&M that I think complex numbers really exhibit their gracefulness in the description of physical phenomena.
Likewise, as lurscher has mentioned, there are formulations of QM that avoid explicit reference to complex numbers -- they are equivalent mathematical representations, but the manipulations have an added degree of bookkeeping that we had already built into complex numbers.
And that's the rub. Complex numbers are a tool for describing a theory, not a property of the theory itself. Which is to say that they can not be the fundamental difference between classical and quantum mechanics. The real origin of the difference is the non-commutative nature of measurement in QM. Now this is a property that can be captured by all kinds of beasts -- even real-valued matrices.