I figured out how to fix this - this worked for both my and my friend's iPhones. 1. Connect to iTunes in recovery mode, start recovery. 2. When you see the "Spinning wheel" on iPhone's screen - EJECT THE CABLE IMMEDIATELY. Wait for 10 seconds 3. Reinsert the cable - the restoration process will begin. Looks like Apple has a faulty algorithm that marks some iPhones as damaged even if they are not(or they simply want you to buy more new devices :)).