Date field index not working when using > operator

Hi we have a database table with about 1 million rows. Quite often we do selects using the greater than operator on a date field so:

SELECT id,user FROM data WHERE pub_date > “2008-06-09”;

We have an index on pub_date , this weekend the query stopped using the index and does a full table scan so if I do an explain it shows almost 1 million rows have been scanned which is very slow and it shows it is not using the key.

Even weirder if I change the date to 2008-06-10 and run explain it uses the index and scans far less rows.

This is very bizare behaviour. I am thinking of doing:

SELECT min(id) FROM data WHERE pub_date = “2008-06-09”;

to get the id to start searching on and then using this in the second query

SELECT id,user FROM data WHERE pub_date > “2008-06-09” and id> idfromfirstquery;

This will obviously force a lot less rows to be scanned, however this isn’t ideal. Does anyone have any idea what might be going on with my date field index?