Были похожие проблемы в проекте с мега16 и ат45, схемы подключения была очень похожа, если не идентична, приведенной, и программатор был тоже STK200 на HC244, может проблема в самом программаторе? Может помехи какие? Программатор у меня дох по линии MISO причем хитро это проявлялось, линия просаживалась до первой операции прошивки программатором и проявлялось в том что не работали операции записи-чтения в ат45 пока к схеме был подключен программатор и до того момента пока я не перешивел мегу - после этого все работало нормально... Еще мое устройство при отладке питалось от импульсного источника питания и мне припоминается, что у моего соседа тоже были проблемы с прошивкой пока работал этот источник...т.е. на лицо влияние помех.
P.S. А куда же делся крутейший программатор AVR910-USB?

P.P.S Тогда я этот вопрос не решил, просто тихо матерился и перешивал по 3 раза

Но при производстве прошивку производили программатором AVR910-COM с довольно коротким шлейфом и проблем, насколько я помню не было...