Regenerating any of the keys helped.

Interestingly enough I regenerated only the Key 2, while used the Key 1 for requests -- in essence, the payload did not change.