Reading around on the web on others having the same issue, I notice that this can happen in cases where users are trying to calculate the request signature themselves manually without using an Amazon SDK, and get it wrong in some way. One particularly common case I have seen is where the secret key contains more exotic characters such as '+' or '/', and they do not URL encode the keys properly before calculating the signature.