Thanks for the quick reply.
What, you don't read minds? ;) The serial config device is set up for AS programming. Both MSEL tied low on the Cyclone II and a separate JTAG connector. Wiring, pull-up and pull-down resistors are all correct.
Switching to the Altera part was my first guess, too. Not sure why we are using the other in the first place. I fired off an email suggesting the EPCS4 at about the same time as I wrote the first post about my problem. I had read the documents you listed - and read them carefully hoping I'd overlooked some tiny detail. Nada.
It's odd only because we've used the M25P40 in the exact same circuit on several designs without a problem.
I'll post a follow-up after the boards come back from the field and I can actually look at one.