I'm following the directions on the API documentation precisely, and after some frustration I finally put together something directly from their examples on http://docs.amazonwebservices.com/AWSECommerceService/2011-08-01/DG/rest-signature.html
I've tried this python script on a few machines and have gotten the same result on all of them.
import hmac
from base64 import b64encode
from hashlib import sha256
secret_key = '1234567890'
to_sign = """GET
webservices.amazon.com
/onca/xml
AWSAccessKeyId=AKIAI44QH8DHBEXAMPLE&ItemId=0679722769&Operation=ItemLookup&ResponseGroup=ItemAttributes%2COffers%2CImages%2CReviews&Service=AWSECommerceService&Timestamp=2009-01-01T12%3A00%3A00Z&Version=2009-01-06"""
print b64encode(hmac.new(secret_key, to_sign, sha256).digest())
The instructions say that the signature using this request, and this key, is Nace+U3Az4OhN7tISqgs1vdLBHBEijWcBeCqL5xN9xg=
but I get O6UTkH+m4zAQUvB+WXUZJeA8bZcKAdkc4crKgHtbc6s=
(Before anyone says anything: The example page displays the requests wrapped at 65 characters; I've already tried it. This doesn't provide a solution, and is not stated in the instructions for signature creation.)
EDIT: I found the answer, see below.