I've recently had a problem where the optimiser has changed it's execution plan to selecting a Full Table Scan as opposed to using a bitmap index (on country_id which contains 12 values in a table with 3.3 million).
To get round this, since the data values are quite skewed... I've run the following:
analyze table .... compute statistics on column ... size 15;
This has now returned the optimiser to select the index.
However, every week we run as a batch job:
analyze table .... compute statistics;