Der Mega könnte defekt sein. Schon mal einen anderen ausprobiert? Außerdem solltest Du es mal probieren, ohne ihn vorher zu erasen.
Welchen Programmer hast Du? Ich hatte schon öfters ähnliche Probleme mit einem JTagICE MKII, allerdings ohne den Grund zu kennen.
Ein-/Auschalten aller Versorgungen kann auch nicht schaden.
Gruß