To spare anyone from going to gfaqs for the fix:
1. (Re)connect your PS3 to the Internet
2. Update date and time via internet
3. In case of inaccuracy, manually change date and time afterwards
There might be -some- loss of data (had to repatch MVC2 for example) but there shouldn't be any significant losses such as saves, etc.