Query Plan far worse in 7.3.2 than 7.2.1

Friends,
I've got a query that has stopped using an index scan between 7.2.1 or RH
7.1 and 7.3.2 or RH 8.0, and I can't figure out why. I've come up with a
replacement query which is a whole lot faster, but again, I can't tell why.

The original query (condensed to remove the uninteresting bits) is:

SELECT COUNT(*) FROM Border_Shop_List WHERE NOT EXISTS (SELECT Foreign_Key
FROM Sample WHERE Foreign_Key='Quantum_' || Border_Shop_List.Assignment_ID
|| '_' || Assignment_Year || '_' || Evaluation_ID)

This runs in 667055.79 msec

The new one is:

SELECT COUNT(*) FROM Border_Shop_List WHERE 'Quantum_' ||
Border_Shop_List.Assignment_ID || '_' || Border_Shop_List.Assignment_Year ||
'_' || Border_Shop_List.Evaluation_ID NOT IN (SELECT Foreign_Key FROM
Sample WHERE Foreign_Key IS NOT NULL)

This runs in 16500.83 msec (~1/40th the time)

Again, my immediate problem is solved, but I'm trying to understand why
there is such a speed difference.

I've attached explains for the two querys in both versions.

The schemas for the two databases are identical. If there's more info
people need, just let me know.

Thanks,
Peter Darley