If these devices are the cause of your problems, you're likely to notice video problems after the computer has been running for a short time. It'll probably be cool when you first power it on, so usually you won't see problems until it's started heating up.
The Atmel and Lattice devices do exactly the same job, you won't notice any difference between them in this application.
Same goes for the speed, even the slowest GAL devices are fast enough for operation in the A3000. There's no advantage in paying extra for the faster rated parts.