С софтом, вроде, нормально... Пока программатор подключен (кирпич подпитывается) рестартует нормально. EEPROM нормально и пишется и читается. Если питание оключается полностью, тогда проблема. В EEPROM забиваются всегда одни и те же значения...
Когда-то давно похожие проблемы были с простыми AVR-ами. Тогда проблему решил с помощью MC33064. Здесь, вроде, BOD должен решать эту проблему, но.... :(