Hey guys, it's taken a few weeks but I've more or less solved it. Firstly, I hooked it up to a Osciloscope and found that the arduino was outputting correctly, my sample rate on the logic analyser was too low to see AND the signals were getting lost as soon as they reached the board due to a shitty breadboard.
So I tried transplanting everything onto a solder breadboard and soldering all the connections. However, when I reflashed the arduino the serial read wasn't showing that the EEPROM had been programmed.
I finally caved and bought an Xgecu T48 Universal programmer. I used Dissy614's binary file from his Google Drive and uploaded it to the EEPROM. I did however find it was only writing every 7th byte when setting the device as an Atmel AT28C16, so following Shyssiryxius's solution to instead set the device as a Catalyst CAT28C16A I was finally able to correctly program the EEPROMS.
I did find that when I first read the second EEPROM with the T48 it had the correct programming so I think that my solder breadboard programmer was working, The arduino just wasn't reading properly. But by then it was too late. The soldered breadboard may have worked but I did rush a few of the connections towards the end and I have the T48 now which definately did the job.