Often with a brand new server, the time is all messed up.

you can check with :

$ date

---

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