MySQL does not use an index for the two-column period

I have a table with millions of rows that has 2 DATE columns that are used to specify a start and end date range. I have a single index for the two columns but it doesn't get used and the query takes 10 seconds to run which is completely unacceptable. My query is simple:

SELECT * FROM `events` WHERE `valid_from` <= "2013-05-05" AND `valid_to` >= "2013-05-05"

Why is this not using the index and taking so long to run?

Edit

An EXPLAIN for the query above:

+----------------------------------------------------------------------------------------------------+
| id | select_type   | table  | type | possible_keys | key  | key_len | ref  | rows     | Extra      |
+----------------------------------------------------------------------------------------------------+
| 1  | SIMPLE        | events | ALL  | valid_from_to | NULL | NULL    | NULL |  2166894 | Using where|
+----------------------------------------------------------------------------------------------------+

---

Check fields order in index and in your query. Also, show

 EXPLAIN SELECT * FROM `events` WHERE `valid_from` <= "2013-05-05" AND `valid_to` >= "2013-05-05"

Try to use index hints

SELECT * FROM `events` USE INDEX (`valid_from_to`)
WHERE `valid_from` <= "2013-05-05" AND `valid_to` >= "2013-05-05"

Or make two indexes for each field instead of one.