I see, you are using the arduino as the programmer for a new chip.. If the arduino is at 16MHz and SPI is /128 it could be too high (125KHz), sure. It would be better to go down to ~1kHz for the new chip fuses reflash.
Factory-fresh chips should be running at 1MHz, so as long as the SPI clock is below 250kHz it ought to be ok.
You could always try using the clock pre-scaler, which can reduce the system clock by up to 256x. eg:
CLKPR = (1<<CLKPCE); // enable clock divider
CLKPR = (1<<CLKPS0); // divide f_cpu by 2
There's always the possibility the new chips are genuinely dead for some reason. A way of ruling out programming problems, albeit high-risk, would be to set the fuses of the working ATmega328p to their factory defaults and then try reprogramming it. Something like this:
avrdude -c arduino -p atmega328p -P COM4 -b 19200 -e -u -U efuse:w:0xff:m
avrdude -c arduino -p atmega328p -P COM4 -b 19200 -e -u -U hfuse:w:0xd9:m
avrdude -c arduino -p atmega328p -P COM4 -b 19200 -e -u -U lfuse:w:0x62:m
(making sure to reset the clock-related fuses last)
Do you have:
1. Xtal connected to the brand new 328p?
If the chip is using its internal clock, as it should be if it's brand new, there's no need to connect an external crystal. OTOH, having a crystal there shouldn't disturb SPI communications. Majenko, could you post a photo of your setup?