Das Einzige, was ich jetzt noch vermuten würde: Die Clock-Fuses haben sich durch nen Übertragungsfehler doch verstellt. Kann gut sein, dass der EEPROM-Bereich mit den Fuses durch die zu geringe Spannung unvollständig programmiert wurde.

Welche Taktquelle hat der AVR denn? Intern oder ext. Quarz?
Falls intern und sofern Zugang möglich/Teile vorhanden: Auf einem 2. AVR (welcher ist egal) einen Pin in ner while(1) togglen lassen und den an XTAL1 vom Mega2561 legen. Wenns wirklich ne falsche Taktquelle war, müsste er jetzt wieder antworten (ISP-Frequenz dabei runterdrehen)

Kannst du testweise den Programmer mal an nem anderen AVR testen bzw. den 2561 ohne laufen lassen? Nicht dass der Programmer nen Hau hat.