It could be the HWM problem. Was the partition once much bigger but has now had most of its rows deleted? If so, you need to rebuild it. If you are on 10g, you can use the SHRINK clause in the ALTER TABLE command. Otherwise you need to rebuild the partition as a separate table and then use the EXCHANGE PARTITION clause to swap the inefficient partition out.
Best way to find out is to use SQL*Trace and TK*Prof. ALTER SESSION SET SQL_TRACE = true;
-- run slow SQL
-- run fast sql
ALTER SESSION SET SQL_TRACE = false;
No go find the trace file and run TK*Prof. Details in the Oracle Performance Tuning manual. If the slow SQL has the same plan as the fast one, and they read the same number of rows (roughly), but the slow SQL has much higher disk reads, then you almost certainly have the HWM problem.
If the difference is not clear from the tk*prof output, post it here for advice.
_____________
Ross Leishman