I was able to duplicate this behavior with dummy data that had only a
few distinct values for fknamestringid --- the planner then thinks that
the index probe into attribute will match a lot of rows and hence take a
long time. Could we see your pg_stats row for fknamestringid, ie
select * from pg_stats
where tablename = 'attribute' and attname = 'fknamestringid';
It would be interesting to see the same for your 7.4 installation too.
regards, tom lane