Often with a brand new server, the time is all messed up.
you can check with :
To avoid all kind of related problem, there is a neat little package called ntpdate which will force the server to sync his clock on a time server :
$ apt-get install ntpdate $ (sudo) ntpdate-debian
If you want to change the timezone :
$ dpkg-reconfigure tzdata