Problem gelöst:

Jetzt habe ich per Zufall das Problem gefunden. Das Auslesen und Setzen der Fuse-Bits geht nicht richtig über den dafür vorgesehenen Knopf. Es funktioniert, wenn man die gesamte Device ausliest, dann über den Fuse-Bit Knopf seine Einstellungen vornimmt und anschließend wieder die Device beschreibt. Habe mit einem Mega32 und mit einem Mega16 getestet, geht bei beiden auf diese Weise.