Fixed it!
It is important that the PRS-505 be FULLY CHARGED before running the firmware upgrade. My PRS505 had two bars, which is less than fully charged. That is supposedly what caused the problem.
For some reason, my USB was not letting the device charge fully at this point. Charged it with an AC adaptor, reran the firmware upgrade and it works.
FYI: The PRS-505 uses the same AC adaptor as a PSP.