I had the same problem and this is what worked for me:
When you launch the game and it prompts to update, cancel. Then the game will ask if you want to connect to the PlayStation Network, select "yes". You will be asked to update again and this time, try the update again.