Use a different flash drive or flash device just to be extra cautious. Select Update firmware from the recovery menu, and then it will prompt you to insert a flash drive with 3.50 firmware or higher.
If that doesn't work, full format the hard drive via your pc, and then try again, if that doesn't work, call technical support and pay $150-$US180 to get the PS3 fixed... or marked the "Krisdog's" comment as best answer and take a hammer to your system.
I second this idea. Download 3.50 again. Do an hash check on it (from what ever website you can find a hash check on (MD5, SHA1, etc...))