On similar problems with upgrades on both the S4 and S3 this have helped:
Go to phone settings-->More, then select Date and Time. Change the date format to something else then change it back to the format you wanted. Save and go back.
I have no idea if this will help on this problem but it might be a thing to try instead of a factoryreset