When you upload a new sketch with the default settings, the EEPROM will be cleared.
"The -e option instructs avrdude to perform a chip-erase before programming; this is almost always necessary before programming the flash."
If you're using the Arduino IDE, the -e option is enabled by default. This is probably why it's not working for you.
See also the question Is there a way to preserve EEPROM contents in AVR Atmega when burning a new firmware to flash with avrdude?
