Ok as I was half expecting, I've been chasing a red herring. The PROMs work fine.
Just to verify, I wrote the contents to an EEPROM I had lying around, and connected it to the same address pins as the one on the PCB. Testing all the output pins, I'm getting the exact same reads as on the PCB...