When you check the plans, what join method is being favoured? Are you seeing "BITMAP CONVERSION TO ROWIDs" in your plans when using b*tree indexes?