It would appear to not be the EEPROM. In the code I posted, I added a array of 512 bytes and wrote to that instead of the EEPROM - I still get the errors.
(I guess I'm assuming that writing to an array in internal SRAM is quicker than writing to EEProm.
Regards,
Mike