Did you burn the Arduino bootloader on the new chips?
From the factory the chip uses the internal 8 MHz Resistor-Capacitor oscillator with a pre-scale of 8 so it runs at 1 MHz. Pert of the bootloader burning process is to set the chip to use the external 16 MHz crystal/resonator with a pre-scale of 1 so the chip runs at 16 MHz.