"SELECT COUNT(*)" is slow, even with where clause

I'm trying to figure out how to optimize a very slow query in MySQL (I didn't design this):

SELECT COUNT(*) FROM change_event me WHERE change_event_id > '1212281603783391';
+----------+
| COUNT(*) |
+----------+
|  3224022 |
+----------+
1 row in set (1 min 0.16 sec)

Comparing that to a full count:

select count(*) from change_event;
+----------+
| count(*) |
+----------+
|  6069102 |
+----------+
1 row in set (4.21 sec)

The explain statement doesn't help me here:

 explain SELECT COUNT(*) FROM change_event me WHERE change_event_id > '1212281603783391'\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: me
         type: range
possible_keys: PRIMARY
          key: PRIMARY
      key_len: 8
          ref: NULL
         rows: 4120213
        Extra: Using where; Using index
1 row in set (0.00 sec)

OK, it still thinks it needs roughly 4 million entries to count, but I could count lines in a file faster than that! I don't understand why MySQL is taking this long.

Here's the table definition:

CREATE TABLE `change_event` (
  `change_event_id` bigint(20) NOT NULL default '0',
  `timestamp` datetime NOT NULL,
  `change_type` enum('create','update','delete','noop') default NULL,
  `changed_object_type` enum('Brand','Broadcast','Episode','OnDemand') NOT NULL,
  `changed_object_id` varchar(255) default NULL,
  `changed_object_modified` datetime NOT NULL default '1000-01-01 00:00:00',
  `modified` datetime NOT NULL default '1000-01-01 00:00:00',
  `created` datetime NOT NULL default '1000-01-01 00:00:00',
  `pid` char(15) default NULL,
  `episode_pid` char(15) default NULL,
  `import_id` int(11) NOT NULL,
  `status` enum('success','failure') NOT NULL,
  `xml_diff` text,
  `node_digest` char(32) default NULL,
  PRIMARY KEY  (`change_event_id`),
  KEY `idx_change_events_changed_object