Someone to correct me if I am wrong BUT
the first query seems to return one row
Operation Object Name Rows Bytes Cost

SELECT STATEMENT Optimizer Mode=CHOOSE 1 38

The second one however returns
Operation Object Name Rows Bytes Cost

SELECT STATEMENT Optimizer Mode=CHOOSE 501 K

I am not very sure, but before stats seems CBO thought the predicate is highly selective, so it used NL join, hoping the system to return just one row.
After the stats, the CBO considers predicate much less selective (501K rows) so it prefers sort merge join, which generally performs better that NL for huge amount of data and supposes Full Table scans for both tables.
What I would ask is , are you sure that the second query performs worse? Full table scan is not always bad