His next best option is to switch to MySQL 5.1 and start making use of partitions.
That's HUGE.
I tried his table layout on my own server with partitions and ~20M rows.
Queries that took 2-3 minutes without partitions took ~5-10 seconds tops with.
Lots of solutions to this issue. count() on an innodb table is just bad news.
A summary table wouldn't be a bad idea at all.. just make a single field table with a value you add/subtract from based upon the addition or subtraction of rows.