You should trace the queries and see what path the optimizer is taking. You also might consider investigating data skew as a source of the problem; if data is very unevenly distributed in a column, the optimizer might be making a bad choice. Consider the use of optimizer histograms if data skew is present.
Whenever you're planning to upgrade statistics, it's a good idea to use DBMS_STATS to save the existing statistics off to another table. You can then switch between the two sets, trace SQL with each, and see exactly how the optimizer's plan has changed.
This was first published in May 2005