Glad to see that your restore points worked.
Sometimes an antivirus program will interfere with those, so if they fail in normal mode, then Safe Mode is the next step.
Personally I'd complain about the condition you have received the replacement in and ask them for another.
With care you may be able to straighten the pins with a needle, but bear in mind you would need to handle the needle with a gloved hand so that you don't transfer static from your body through the needle.
Even then, when you come to insert the CPU they may still not be fully aligned and bend again, but here are a couple of other methods you could try -
http://www.wikihow.com/Fix-Bent-Pins-on-a-CPUGet another RMA would be my best advice though.