We found out through tracing etc that the optimizer is behaving strangely. Its choosing an explain plan that is not completely optimal. There's something funny with statistics as well, since when I rewrote the query to use the rule based optimizer, the query was finishing much much faster.
So, we had to do some experiments with Oracle traces as well. Help on Oracle's tracing mechanisms and ideas came from
Introduction to Oracle Trace Utulity and Understanding The Fundamental Performance Equation « H.Tonguç YILMAZ Oracle Blog
Working together with our in-house DBA team helped a bit and I moved forward with some more experiments. Here's what helped me with Optimizer in Oracle (mostly CBO)
Oracle Optimizer: Moving to and working with CBO
Oracle Optimizer: Moving to and working with CBO - Part 2
Blogged with the Flock Browser