that's right. thanks for the correction.
if uploading sketch via bootloader, the avrdude command is like
avrdude -CE:\arduino-1.0\hardware/tools/avr/etc/avrdude.conf -v -v -v -v -patmega328p -carduino -P\.\COM1 -b115200 -D -Uflash:w:C:\TEMP\build3958906321873940373.tmp\Blink.cpp.hex:i
which is independent of the fuse setting as you said.
if you say burn the bootloader, the avrdude command is
avrdude -CE:\arduino-1.0\hardware/tools/avr/etc/avrdude.conf -v -v -v -v -patmega328p -cstk500v1 -P\.\COM1 -b19200 -e -Ulock:w:0x3F:m -Uefuse:w:0x05:m -Uhfuse:w:0xde:m -Ulfuse:w:0xff:m
the fuse values are obtained from board.txt, so you can either change it in boards.txt or just run avrdude from command line with the fuse values needed.
now come to think of it, I think the OP problem is not due to fuse setting. I think the db library may be clearing the eeprom. 