mturk API gives "specified claims are invalid" message about half the time; resubmitting randomly fixes

I'm using a custom PHP script to submit requests to the mturk API, based on the signature functions from the PHP-AWS library. Here's an example of a request:

http://ift.tt/1LE8Zxb

Sometimes a given script will work, and at other times the same script will return an error like this:

AWS.BadClaimsSupplied The specified claims are invalid. Based on your request, your signature should be generated using the following string: AWSMechanicalTurkRequesterNotifyWorkers2015-06-25T09:37:51Z. Check to make sure your system clock and timezone is not incorrect. Our current system time: 2015-06-25T09:37:51Z. (1435225071849)

When I get this error, repeatedly regenerating and resubmitting the call will cause it to eventually work. That is, the API returns true and the desired action is taken, or it returns an error due to some other problem with the request.

I assume that if I were performing the hash incorrectly or with the wrong signature, then it would never work*. The intermittent nature of the problem points to a timing error. But the example above shows an error message in which the time I used for my signature is the same as their time, so that doesn't seem like the problem either.

*okay, it would work once in every 2^160 tries.

I tried backdating my timestamps by 1 second just in case I was a little ahead of them; that didn't change the results. I can't think of any other way to debug this.