This issue has been fixed in Nios® II 6.0.
The Nios II Flash Programmer may issue this error while attempting to program lead-free EPCS serial flash devices. The lead free versions of EPCS1 and EPCS4 (indicated by an 'N' in the part number) have different RDID identifiers than the non-lead-free versions, which causes the Flash Programmer to fail.
If you encounter this issue with Nios II version 5.1, download this zip file containing the modified override file and extract it into "<nios2 install dir>/bin". Attempt to program the EPCS device again. This will force the flash programmer to recognize the new RDID identifiers.
EPCS16N and EPCS64N are unaffected.