We had kind of the same problem - the problem arose because we started using a flash from Spansion. The flash supports the CFI format/protocol, but unfortunately, the Spansion flash is more picky about CFI, and thus we experienced the same problem.
What happens is that the programmer will download a "flash programmer" design to your board, it will then use the CFI functions to figure out how the flash is configured (banks, sizes etc). Finally the flash chip will be programmed. We kept getting the error message you mentioned, so...
We then tried to program the flash by downloading a small program via JTAG, the program would try to write stuff to the flash using the alt_flash functions.
This kept failing, so singlestepping through the code, we realized that the alt_flash_ functions did not work with the Spansion flash, since we have the source code, we where able to fix the error.
I suggest you make a small "hello, world" type application, and then try to open, and write stuff to your flash. Try singlestepping through the code (inside the alt_flash_ routines), and figure out why it fails.
But at some point, the flash programmer should be recompiled so that it will work with other CFI flash devices.