NSD es el comportamiento normal ya que las tablas innodb no llevan un conteo interno de numero de registros:
Cita: InnoDB does not keep an internal count of rows in a table because concurrent transactions might “see” different numbers of rows at the same time. To process a SELECT COUNT(*) FROM t statement, InnoDB scans an index of the table, which takes some time if the index is not entirely in the buffer pool. If your table does not change often, using the MySQL query cache is a good solution. To get a fast count, you have to use a counter table you create yourself and let your application update it according to the inserts and deletes it does. If an approximate row count is sufficient,
SHOW TABLE STATUS can be used. See
Section 14.2.12.1, “InnoDB Performance Tuning Tips”.
Fuente:
http://dev.mysql.com/doc/refman/5.0/...trictions.html
En resumen phpmyadmin hace un estimado.