Just a "stab in the dark", but if your table is hash partitioned and your query allows partition pruning, then you need partition-level statistics gathered.

The DBMS_STATS procedure ought to have gathered both table and partition-level stats, but it'd be worth checking that the partition stats are there and that they appear reasonable.