ttp://dev.mysql.com/doc/refman/5.1/en/innodb-restrictions.html
の真ん中へんにあるように、InnoDBはrowの数を保持してないのですよ。
（MyISAMは保持してるので速い）

>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.

とか書かれちょります。
　あとは「更新頻度が低いならクエリキャッシュを使え」とか、
正確でなくていいならSHOW TABLE STATUSを使うのもいいんじゃねとか、そんな感じ。

　MyISAMのほうが速いのを利用して、レプリケーション先をMyISAMにして
そっちでcount(*)する技もないではない。

　お好きな方法をどうぞ。