Apparantly the total design has quite a lot of timing errors (and I mean 1000s) for signals that cross between clock domains (not related to these nios cpu and their memory). Some of these signals are trully 'don't care' (eg led outputs), some are probably synchronised - but the tools haven't been told, and others will be bugs waiting to strike!
Marking about 7 clock pairs as 'false paths' (all related to a specific 96MHz clock generated from an external 8MHz input) lets the rest of the fpga be synthesised without any timing errors - and the 'failing' board passes the test it was failing on.
The suspicion is that in attempting to meet these impossible timing constraints so much fpga real estate was used that other paths also failed.