Thanks for your answer Slacker,
I don't think we have any DMA in our nios system. We have been messing around with the waitstates: we changed the tcl file provided by altera, regenerated the core, look at the read and write ops and those times were increased according to what we set. When we tried again to program it did not work. However, we did one last change; we incremented the setup and hold times (they were set to 0 by default) to at least 1 cycle through the tcl file. And now it works! It looks like that was what was causing the issue, which would make sense. I hope this can help other users, too.
Thanks a lot for pointing us in the right direction!