Have you seen this error, everything on the web points to a time and date issue. This is clearly not the case for a lot of people.
What I did to resolve this was to erase the phone via the Settings > About menu and start afresh. Now the phone is able to update itself. I also did not do a restore from the last backup, I just signed in after the phone was setup.
Another thing I did too was to remove the SIM card, so everything updated over Wi-Fi