若干乗り遅れていますが、
B-ShoppingもAffiBook!!も対応しなければいけません。

要は
http://docs.amazonwebservices.com/AWSECommerceService/latest/DG/index.html?rest-signature.html
をやれと言うことですね。

http://d.hatena.ne.jp/niiyan/20090509/1241884365
を参考にやってみました。

リクエスト先も
http://ecs.amazonaws.jp
から
http://webservices.amazon.co.jp
に変わっているんですかね。

クエリの組み立ては、下記のようにしていたので、単純にそれで作られるListの
sort()でやりました。
   query = [
       (‘Service’, service),
       (‘AWSAccessKeyId’, accessKeyId),
       (‘Operation’, operation),
       (‘SearchIndex’, searchIndex),
       (‘ResponseGroup’, responseGroup),
       (‘Keywords’, self.params.get(‘Keywords’, None).encode(‘utf-8’)),
       (‘AssociateTag’, associateTag),
       (‘Version’, version),
       (‘Timestamp’, timestamp),
   ]
   query.sort()

とりあえず返ってきているので、良しなのでしょうか（ちなみに、このsort()を
しないと返ってこないので、効いているようです）。