Is it possible that at some early stage of your program launching that you are either intentionally or mistakenly starting a EEPROM write cycle?

If so an attempted read will be locked out for as long as the write operation was in its self timed process to completion. This is what could be what makes some reads appear to fail.

You should add some test code that checks to see if the EEBUSY bit in the EECON register is set just before you attempt to read each byte from EEPROM. If this bit is set then turn on some testing mode LED or other debug mode I/O signal to alert yourself as to the error. Have the program stop at that point in a hard loop so you can observe the error LED/IO being set. (Of course make sure you initially take care of the default state of this LED or I/O signal so that is is "off").

Michael Karas