Apple has posted a support document which offers a possible solution.
This can occur if the iPhone is not displaying the same date and time setting as the carrier network time.
Make sure iPhone is setup to receive the network time. Choose General > Date & Time and turn Set Automatically to ON. (Note that in some locations, network time may not be available and in some cases, you may not see this option)./q>