I've just experience a similar problem to OP as this is the first time I've tried to play TLOU.
The game prompts an update to 1.05 is available but I was constantly getting a server error 503 or 504 even when waiting for the hard drive yellow light to stop blinking.
I even tried restoring the PS3 file system as mentioned in this thread however none of it worked.
I ignored the update so the game logged me off PSN and continued to load from a brand new game disc.
After selecting the language option, press start to bring up the menu and started a new game.
Once the first cutscene is finished and you are in control of Sarah in her bedroom, I did a manual save and exited the game.
When back at the XMB, start the game and it will prompt an update to 1.05 again. I only waited about half a minute and then pressed X to continue downloading the update.
This time the download actually started and after about a 111MB download I now have TLOU 1.05 installed.
I hope this helps, good luck.