I had the same problem and searched all over the web but nothing worked (reinstall, delete patches and start without them, PS3 safe boot with database rebuild, start without internet connection). Finally I found the issue myself:
Turns out the disc that I had bought used was super crabby. After I removed all the sticky stuff and fingerprints with water and a soft cloth, the game started like a charm.
The symptoms before:
Stuck on black screen with TLoU logo in the bottom right corner, no reaction from the hard drive (drive light permanently off)
Black screen with TLoU logo showed up, but hard drive light kept flickering for about 30-60 seconds, then the game booted up flawlessly.
Well that success didn't last long. After I passed the screen with the logo at the bottom right I got to the main game screen where I was able to start the game. Then I got stuck on the spore screen (loading x.xx%). Bummer.
Apparently the numbers take a long time to go up, but in my case they suddely went to 0.00% and stayed there. After a few reboots the game force restarted every time I loaded it up.
When it did, I had to do a safe boot with database rebuild, delete the game files and could try again, but ended up with 0.00% again.
My guess is that the disc, while clean now, is too scratched and the game doesn't have a very robust installation routine to counter that.
I may try getting another copy of the game.
Update: I bought a new used disc which solved my problem. It seems to me the game is not dealing well with scratched or dirty discs, so if all else fails and you can't get the game to run after properly cleaning the disc, try getting a new one in good condition.