При включенном питании и последующей прошивке Atmega644-20PU программатором (AVreal1.25) устройство работает согласно заданному алгоритму..и все в порядке.
После выключения/включения питания алгоритм начинает глючить (работает по другому). Как будто Flash грохается.

Подскажите пожалуйста с чем это связано?

RESET проверьте. ПРи включённой сбросьте её ручками и посмотрите как будет работать и на какой частоте она у Вас пашет

На плате есть кнопка RESET...уже пробовал эффект тот же.
Тактовая частота 16 МГц (от кварцевого резонатора)

Сбросьте HEx или код и дайте контрольную точку - зашью свою , посмотрю, что будет с моей.
В своей микрухе я уверен - глюки за ней не заменчены.

а перефирии никакой нет на плате на SPI? типа датафлешки с которой надо считать что то? Попробуйте включить ваш прибор отключив программатор от схемы.