a) When you say "uses an index", do you mean a local or global index ?

b) Is the index quite selective ?

c) Do the two partitions have roughly the same amount of data ?

d) Is it a bitmap index or a btree index ?

e) Have you analyzed the table as a single unit or have you analyzed each partition separately ? Have you done a "for all indexed columns" to get the histogram data ?