You don't perhaps got the latest firmware 2.4 on there? It causes problems with some PS3 and the only solution would be to rip out the HDD and format it with your PC. When you put it back in the PS3 it wil lask if it can format your drive since the PC created a different filesystem from what the PS3 uses.
Getting it out is real easy, check on the side of the PS3, open the flap, unscrew one screw and pull it out with lever. If you got the money just go buy a bigger one now and put that back in will save you from deleting stuff down the road (though 80Gb should probably be enough. I got a 200Gb in mine and after all the music, demos, and game installs I got bout 70Gb left on it.