Suddenly Eclipse started throwing this error at me while doing Android development.
The Android SDK generates a debug certificate which is only valid for 365 days, not quite what that is for, but to get rid of the problem:
Delete the file ~/home/.android/debug.keystore
Plus clean your project (Project|Clean..)
Afterwards you should be fine and also find a new debug.keystore (for the next 365 days)