Follow these steps (text version of the video):

Accessing the PS3 recovery menu.
1. Turn off Playstation®3.
2. Hold The power button down; The system will turn on and turn off once again.
3. Once the System has been shutdown, re-press you finger until you hear 2 consecutive beeps
4. When you hear the 2 beeps take finger off power button.
5. You will be promted to plug in your controller via usb and then hit the PS button
6. The Recovery menu will pop up.

Once in recovery select "Rebuild Database".