As estatísticas da tabela (usadas pelo EXPLAIN) são baseadas em valores armazenados em cache do sistema que podem não ser precisos.

http://dev.mysql.com/doc/refman /5.1/en/using-explain.html diz:

Portanto, a versão 'count()' da consulta será precisa, pois realmente 'contará' as linhas existentes. A versão 'explain' não conta necessariamente suas linhas, mas pode usar uma estimativa/cache. O Explain não se destina a ser realmente usado em código ou produção - é apenas uma ferramenta para ajudar a analisar suas consultas.