MySQL taking forever 'sending data'. Simple query, lots of data

I'm trying to run what I believe to be a simple query on a fairly large dataset, and it's taking a very long time to execute -- it stalls in the "Sending data" state for 3-4 hours or more.

The table looks like this:

CREATE TABLE `transaction` (
 `id` bigint(20) unsigned NOT NULL AUTO_INCREMENT,
 `uuid` varchar(36) NOT NULL,
 `userId` varchar(64) NOT NULL,
 `protocol` int(11) NOT NULL,
 ... A few other fields: ints and small varchars
 `created` datetime NOT NULL,
 PRIMARY KEY (`id`),
 KEY `uuid` (`uuid`),
 KEY `userId` (`userId`),
 KEY `protocol` (`protocol`),
 KEY `created` (`created`)
 ) ENGINE=InnoDB AUTO_INCREMENT=61 DEFAULT CHARSET=utf8 ROW_FORMAT=COMPRESSED KEY_BLOCK_SIZE=4 COMMENT='Transaction audit table'
 

And the query is here:

select protocol, count(distinct userId) as count from transaction
 where created > '2012-01-15 23:59:59' and created <= '2012-02-14 23:59:59'
 group by protocol;
 

The table has approximately 222 million rows, and the where clause in the query filters down to about 20 million rows. The distinct option will bring it down to about 700,000 distinct rows, and then after grouping, (and when the query finally finishes), 4 to 5 rows are actually returned.

I realize that it's a lot of data, but it seems that 4-5 hours is an awfully long time for this query.

Thanks.

---