The last few characters in the p/n indicate the package type, so your new p/n looks better.
That being said, I've not used those chips before. However, as it's Flash and not EEPROM,
are you sure you're using the correct sketch, and that the sketch can handle the large
address space and timing delays correctly?
I'm sure that losing Vcc while programming will mess things up, but I wouldn't think that
would be fatal to the chip - I may be wrong, other people may know about this.
Also, do you have the WP pin at the correct level?