Try entering Recovery mode using these steps:
1. With the system in standby mode. Press and hold the power button down until the system turns on and then off again. Release the power button.
2. After about 1 - 2 seconds press and hold the power button again, until you hear 2 consecutive beeps. Release the power button. During this step you will actually hear three beeps. There will be one single beep then a short delay followed by 2 consecutive beeps. Only release the power button after you hear the 2 consecutive beeps.
At this point the PS3 Recovery Menu will be shown on the screen.
Select Rebuild Database from the menu.
If this doesn't work, download the 3.60 (fixed) PUP and try to update the Firmware from the recovery menu.