Hast du auch die Fuses geändert sodass der 16MHz Quarz aktiv ist?
Da die Baudrate des Bootloader fix vorgegeben ist, muss auch die Taktfrequenz stimmen.