If I read Jesse right, the problem is in Nios' Data Master. It is not "Latency Aware" meaning it does not monitor 'readdatavalid'.
Soooo, with only static timing at it's disposal, the Data Master must use the same absolute worst case timing for each and every read.
Privately I've been shown that read performance is still a dismal 5-6 clocks from initial access to 'readdatavalid' even when accessing the same row back to back.
I'd really like someone to explain the "single cycle access" statements that are given in Nios classes and docs. Better yet, make the statements come true
http://forum.niosforum.com/work2/style_emoticons/<#EMO_DIR#>/smile.gif
Ken