Table with 400000 rows takes a long time to count

I have a table with 400000 rows and when I do a:

SELECT count(*) FROM table1;

it takes over three minutes to come back - the table is already
indexed off the unique primary key id, which is of varchar type.

MySQL is of version 5.0.22 on a CentOS system.

I thought that MySQL, at the least, would do the SELECT count...
without me having to deal with new indexes.

I ran a mysqlcheck --o db1 table1, but that did not seem to do
anything for it.

Any ideas?

Funny when I do an EXPLAIN SELECT COUNT(*) FROM TABLE1; the query
returns immediately, and it shows that it is using the primary index,
and also that there are 4000000 rows from the query.