Try the following:
1. Go to the iPhone Settings App (your phone settings)
2. Select General
3. Select Date & Time
4. Enable Set Automatically
(5. If its already enabled, disable it, wait a few seconds and re enable it)
I tried your following but still the same error message