The memory test includes DMA transactions...."if" your system has a standard Avalon DMA in it. The DMA portion will hit the memory much faster back-to-back than any of the other tests. You should not skip this portion/feature of the memory tests..
You may be dealing with a situation where Nios II read master transactions are successful, but instruction master "fetches" are failing.
You could also just try adding a few read or write wait states to see if that helps to get the Nios II executing from the offchip memory. You can tune it later on.
Cheers,
slacker