AWS4-HMAC-SHA256, also known as "V4," is one of two authentication schemes in S3.
US-Standard, and many -- but not all -- other regions, also support the other, older scheme, V2.
Frankfurt was introduced late in 2014, it does not support V2.
http://docs.aws.amazon.com/AmazonS3/latest/dev/UsingAWSSDK.html explains how to enable V4 in the various SDKs, assuming you are using an SDK that has that capability.
I would speculate that some older versions of the SDKs might not support this option, so if the above doesn't help, you may need a newer release of the SDK you are using.