Why is the leftmost subset of a key not being used

Server version:

[root@cat best]# /usr/libexec/mysqld --version
/usr/libexec/mysqld  Ver 5.1.47 for redhat-linux-gnu on i386 (Source distribution)

Schema:

CREATE TABLE `Log` (
    `EntryId` INT UNSIGNED NOT NULL AUTO_INCREMENT,
    `EntryTime` TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP(),
    `Severity` ENUM(
        'LOG_LEVEL_CRITICAL',
        'LOG_LEVEL_ERROR',
        'LOG_LEVEL_WARNING',
        'LOG_LEVEL_NOTICE',
        'LOG_LEVEL_INFO',
        'LOG_LEVEL_DEBUG'
    ) NOT NULL,

    `User` TEXT,
    `Text` TEXT NOT NULL,

    PRIMARY KEY(`EntryId`),
    KEY `TimeId` (`EntryTime`,`EntryId`)
) ENGINE=InnoDB COMMENT="Log of server activity";

Query:

SELECT 
   `EntryId`,
   `EntryTime`, -- or, ideally: UNIX_TIMESTAMP(`EntryTime`) AS `EntryTime_UnixTS`
   `Severity`,
   `User`,
   `Text`
FROM `Log` 
ORDER BY `EntryTime` DESC, `EntryId` DESC
LIMIT 0, 20

According to the execution plan (and observation), the index is not being used:

id  select_type  table  type  possible_keys  key  key_len  ref  rows  Extra
1   SIMPLE       Log    ALL   \N             \N   \N       \N   720   Using filesort

I've tried re-organising it a few ways with little success but, more than anything, would like to understand why this simple approach is failing. My understanding was that a left-most subset of any key can be used to optimise an ORDER BY operation.

Is my index wrong? Can I optimise the query?

Please note that I will also want to conditionally add, e.g.

WHERE `Severity` <= 'LOG_LEVEL_WARNING'

though I'd like to get the basic version working first if this makes the solution very different.

Reproduced on SQLFiddle under MySQL 5.5.32.

The reason is that you index includes the primary key in it. and since it is InnoDB, by default the PK is ancluded in all other indexes as the left-most field. i.e. the index in this case is (EntryId, EntryTime, EntryId).

The solution is to have this index only on (EntryTime):

alter table Log drop index TimeId;
alter table Log add index TimeId(EntryTime);
explain SELECT     `EntryId`,    `EntryTime`,     `Severity`,    `User`,    `Text` FROM `Log`  ORDER BY `EntryTime` DESC, `EntryId` DESC LIMIT 0, 20;
+----+-------------+-------+-------+---------------+--------+---------+------+------+-------+
| id | select_type | table | type  | possible_keys | key    | key_len | ref  | rows | Extra |
+----+-------------+-------+-------+---------------+--------+---------+------+------+-------+
|  1 | SIMPLE      | Log   | index | NULL          | TimeId | 4       | NULL |   20 | NULL  |
+----+-------------+-------+-------+---------------+--------+---------+------+------+-------+

HTH