I have tried a variety of things all afternoon to no avail.
It turns out I am not the only one having this problem:
Unfortunately no solution posted there.
Then I stumbled across this little gem of a forum post:
Quoting from the poster:
"Here is what I am told in a tech support email from Digilent: 1. Nexys4 cannot be programmed with current version of Vivado. We hope problems will be resolved in the next version. Read more on http://www.xilinx.com/support/answers/57385.htm 2. Adept is not able to program Nexys4. And it won’t be. 3. Use iMPACT for programming. They couldn't be bothered to put this very relevant information into their user manual."
Yay. This would have been really handy to know.
To add to the intrigue and frustration, the URL they point to redirects somewhere useless now, so the answer isn't even directly accessible.
Digilent have updated the user guide for the Nexys4 since I got my board, but there is no collated errata section for me to work out what has changed, and reading every word to compare two 28 page documents isn't that thrilling a prospect.
The updated reference guide is here.
Now that I know what I am looking for, I can see that they have updated the relevant text on page 5 - 6 to now read:
"Quad-SPI programming can be done using the iMPACT tool included with ISE or the labtools version of Vivado."
This suggests that the latest version of Vivado should be okay, although I am at a loss to know what "labtools version" means. I hope this doesn't mean it isn't in the free version. Downloading Vivado isn't for the light hearted, however, as it is several GB just to download. I will need to enlarge my Linux VM to even try. Maybe I will just form my Linux VM off and reinstall.
Anyway, it suggests that I should be able to program the thing using iMPACT in ISE. This would be great except that I run iMPACT from in a VM on my mac, and so it can't see the USB programming cable. Some sort of dual-boot would be the other option here. I do have ISE on an older Windows machine here, but haven't succeeded in getting that to program the thing either.
Anyway, currently frustrated with the process, but will keep prodding my way around to find a solution.
End of necessary venting of frustration.