I'm going to summarize what is said in the comments and my own remarks about the update, to make a complete answer:

The algorithm suggested in the update is basically checking lower-order coefficients of the composition.  Certainly if the exponents are in binary, then the algorithm doesn't work:  It takes exponential time to distinguish $x^n$ from $0$.  Even if the exponents are in unary, it takes exponential time to distinguish $x_1x_2\ldots x_n$ from $0$.

The [paper of Ibarra and Moran][1] places a more general problem, the word problem in the sense of circuits or straight-line programs, in co-RP.

A straight-line program is a sequence of formulas arranged like a tax form.  It's a sequence of intermediate variables defined by formulas.  It's equivalent to an arithmetic circuit.  It's an interesting definition for groups as well as for polynomial arithmetic.  It is more general than the stated question because it's easy to decompose a polynomial with listed terms into a circuit --- the only hard part is exponents in binary and you can do that by squaring up --- and composition of polynomials can be implemented in a straight-line program by the definition of a straight-line program.

The complexity class BPP means yes-no questions answered in polynomial time by a randomized algorithm which gives a probably-correct answer, with probability $p > c > 1/2$.  The complexity class RP is the same thing, except that if the program answer yes, it is certainly correct; if it answers no, it is only probably correct.  The probability of correctness can be amplified to very close to 1.  It is a well-known conjecture that BPP = P, and obviously BPP contains RP and RP contains P.  The basis of the conjecture is that good pseudo-random number generators seem to exist.  However, there are strong theoretical reasons that even RP = P is a very hard conjecture.

Ibarra and Moran give a polynomial-time algorithm in RP to show that an arithmetic circuit over $\mathbb{Q}$ (say) is non-zero.  (So there is an algorithm in co-RP that the circuit *is* zero -- this is just switching "yes" and "no".)  The algorithm consists of plugging in large values at random.  It is a bit easier to see what they do over $\mathbb{Z}$, and not really different because you can reduce $\mathbb{Q}$ to $\mathbb{Z}$ by decomposing fractions into numerators and denominators.  They make an exponentially large box in $\mathbb{Z}^n$, and they show that if the circuit is non-zero, then it is usually non-zero in the box, using simple (but skillful) counting estimates for zero values.

[Kabanetz and Impagliazzo][2] show that some of the same strong theoretical difficulties that obstruct the conjecture that BPP = P or RP = P, also make it hard to test circuit equality in P.  So you should recognize Ibarra-Moran as efficient in practice because it is in co-RP, believe that Ibarra-Moran can be converted to P using pseudo-random numbers, and be satisfied that no one can provably find any algorithm for the problem in P.

  [1]: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.129.5387&rep=rep1&type=pdf
  [2]: http://dx.doi.org/10.1007/s00037-004-0182-6