Usually when you replace the PAL chips with GAL's they run alot cooler.Are you sure the replacements are GALS? Are the GAL replacements at least as fast or faster than the originals?maybe a bad replacement chip?
>>>> I got GAL U202, U203, U714 replacements from....Anthony Hoffman so I'm sure its ok.
Yes, those parts are modern equivalents to the original programmable logic. They can run faster, draw less current and as a result will dissipate less heat.
Reseating all the socketed devices is a good suggestion, plus it doesn't cost anything. Be careful not to bend legs when re-inserting, etc.
Personally I wouldn't expect it to be a capacitor related issue. While the electrolytics do reduce in capacity with age and heat, I wouldn't expect such a capacity loss to cause that much grief. Maybe if the capacity were to reduce more than 50%, although that kind of reduction is unlikely in all of the electrolytics in only 20 years or so.
All of the high frequency decoupling is done using ceramic and monolithic capacitors, the small blue/yellow ones by each IC. These devices are very stable with heat and age and would have degraded very insignificantly.
Another suggestion is to remove the case cover from the A3000 to help test the heating theory. Although this stops the fan drawn air circulation, it does promote convectional air flow. One of my A3000s tends to start having heat related problems similar to what you describe after a few hours running. Without the case cover on it seems quite reliable though. Does have a lot of crap installed in there, Cyberstorm mk2, Picasso IV, etc, etc. Not surprising that air circulation is poor and heat buildup is an issue. Never did solve the problem, the A3000 only gets infrequent use as it's the backup for the main computer (A4000T).
Last suggestion is send it down here to Antarctica

I've only seen it down to -30C so far, but it'll get colder during winter. If that doesn't keep the A3000 cool then nothing will!