Signing S3 urls fails (The request signature we calculated does not match the signature you provided. Check your key and signing method)

I'm trying to generate signed URLs to upload and download objects in my S3 bucket, but it fails with "SignatureDoesNotMatch" as per below.

<?xml version="1.0" encoding="UTF-8"?>
<Error><Code>SignatureDoesNotMatch</Code><Message>The request signature we calculated does not match the signature you provided. Check your key and signing method.</Message><AWSAccessKeyId>AKIAJ66RWEJPYWX6PL2A</AWSAccessKeyId><StringToSign>GET

I understand that this is a symptom for the problem described here

Amazon MWS - request signature calculated does not match the signature provided

that is, my credentials is somehow wrong. I double checked my .aws/credentials file and generated new ones. Moreover, I can do other AWS operations with these credentials, such as querying dynamoDb or listing my buckets.

The code I use to generate the URLs, I copied from here:

http://ift.tt/1eWGRmY

final ZonedDateTime expiration = ZonedDateTime.now().plusSeconds(expirationSeconds);

final GeneratePresignedUrlRequest generatePresignedUrlRequest = new GeneratePresignedUrlRequest(
    bucketName, objectId.toString());
generatePresignedUrlRequest.setMethod(isUpload ? HttpMethod.PUT : HttpMethod.GET);
generatePresignedUrlRequest.setExpiration(Date.from(expiration.toInstant()));

return amazonS3Client.generatePresignedUrl(generatePresignedUrlRequest).toURI();

And, yes, my bucket exists. How can I get to the bottom with this?