Weird :confused: my PS3 starting running 'slow' 4 days ago and eventually did not boot correctly (did not display warning message and stopped on blank) so I had to unplug it, once it rebooted it insisted it was corrupt and wanted to format, then it insisted the format had failed and wanted to restore which I could not let happen.
I turned the system off and removed the HDD. I put the HDD into my PC and booted up, I had to enter disk management to detect the drive and then format it to NTFS. Once done I removed the drive and put it back in the PS3 for a factory format which it managed to do, it then wanted me to install a FW 2.16 or higher via USB (similar to your scenario) which I did via my USB and then it formatted 2 more times before successfully installing the FW. After that it took me through the first time PS3 setup as if I just bought it and I was on 3.55

Now on 4.70.1 D-REX and installing all my games again... Just a little story
In your case just re-install your firmware when it says via USB.