Additional information: It seems to be related to clocking, so I'll explain my clocking setup (that has not changed since it was initially designed ages ago and was worked for years):
External Clock is 12.288MHz, N is 1, M is 32/2, resulting in a PLL frequency of 393.216MHz, which is in the valid range of 275..550MHz. CPU clock divider is 4, so the CPU clock is 98.308MHz. Everything is in spec, and it worked for ages.
With the newer chips, reducing the input clock down to 6.144MHz makes them work - except that everything works slower (as expected), and the PLL is below spec.