[RequestTimeTooSkewed] The difference between the request time and the current time is too large.

One of my auto backup scripts to S3 suddently stopped working with the error:

[RequestTimeTooSkewed] The difference between the request time and the current time is too large.

After a bit of digging around I noticed on the server if I issued the command:

date

I would get a wildly out of sync time.

To solve this I used the following command as root:

ntpdate us.pool.ntp.org

After this the time was synced and the backup worked again