Damaged hard drive or a scratch on the disk? Can't think of anything else, really.
Does the PS3 have something like a cache? I know that, on the 360, emptying the cache can help with stuff like this.
Second hand PS3?
nope
unless i got con.....but i doubt so since i got it from a reputable store
Still could be damaged from transport. I would suggest looking at the disc and see if there are any scratches then if not then it's most likely the HD.
Brand new ps3?
Did it said "rebuilt" somewhere?