Bad Query Performance With Global Non-Partitioned Index?

I have a partioned (by row_create_date) table, lets called it TABLE_X, which has about 300 million records. This table has 7 columns including the primary key and a non-unique, locally partitioned column called trace_id; 99% of queries access this table via this column.

Lately, querying TABLE_X via the trace_id has been very very bad. Queries run for over 1 hr in some cases. So we decided to change the index for trace_id to a global index. Now queries against TABLE_X return in seconds. So far so good.

However, when the query has to join TABLE_X to another table, the query sometimes runs for over 1 hours; back to the same old problem. Here is an illustration;

SELECT COUNT(1) FROM TABLE_X WHERE TRACE_ID = 'XXXXX';
-- returns in seconds
SELECT COUNT(1)
FROM TABLE_X,
TABLE_Y
WHERE TABLE_X.TRACE_ID = 'XXXXX'
AND TABLE_X.TRACE_D = TABLE_Y.TRACE_ID;

-- runs for over 1 hr, even when TABLE_Y.TRACE_ID is a primary key.