Ok, this is an SPI serial eeprom. It has various levels of hardware protection, but it also has a software write disable command. You first enable it with a write enable, make your change, and then disable it. Are you disabling it after each write?
The spi interface is such that if there is noise on the clock pin, it's conceivable that if you left the thing selected, and in write mode, that it could write a random byte. The write opcode is the cleverly chosen
0000x010. Clocking the thing enough times to output the address and data (then raising CS at just the right time) might cause problems.However, I'm still guessing it is a software problem. You are writing the bad data. You can prove this to yourself by keeping a shadow copy of the data elsewhere in the eeprom, assuming there is enough room. If it's bad in both places, you are writing it.
Also, disable writes after you change the data, if you aren't already doing it.
One other idea is that if you continually rewrite the same cell, it can run out of lives. The cells will only last for a certain (large) number of writes. Flash file systems typically rotate the flash pages to prevent this sort of problem. If, for example, you are putting the checksum in the same place, and rewriting it again and again on a moment to moment basis, you can cause the cell to fail.