What are your Input and output clocks?
A few years ago I was using a DCFIFO on a Cyclone 1 where the rd clock and write clock were supposed to be the same frequency, but because they were derrived from different clock inputs, they had potential phase and PPM differences. (It was an onboard 28.93 MHZ crystal and a recovered 28.93 MHz clock from a fibre optic link). This was buffering video data. The DC FIFO was async reset at the end of every line. Over/underflow protection were turned on IIRC.
Every now and again, the data in the FIFO would repeat itself, looking like the read counter was overflowing. I fixed it by using a custom fifo that wouldnt allow data to be ready until it had a minimum number of values in the memory (I set it to about 8), so that I wouldnt get over/underuns.