Hast Du denn nochmal nachgerechnet, ob die von Dir gewünschtern Verzögerungen (_delay_xx(..)) in Deiner Software auch tatsächlich richtig ausgeschrieben sind?
Wenn wir davon ausgehen, dass der Prozessor tatsächlich mit 16MHz läuft, was er laut ja wohl tut, wie Du anhand der Fuses und der Quarz-Experimente gezeigt hast, sehe ich da eher ein Software-Problem.
Hast Du mal im vom AVR Studio generierten Makefile nachgesehen, ob dort tatsächlich etwas wie "-DF_CPU=16000000UL" steht?