As Cardano is not cool enough to have a Linux wallet, I had to install Daedalus on a Windows 7 machine and once having done that, I ran into the above issue. This is how to fix it.
Be sure to run Daedalus by clicking "daedalus.bat" within the install dir.
If that doesn't do it either, make sure your PC synchronizes time by the server "time.windows.com" and then start Daedalus again.
That worked for me.
If this helps you, pls vote me up :-)
Honestly, Cardano, this is embarrasing...
Cheers.