Some time ago (after noticing my stuff was not working anymore 
), I wrote a Utility Class for the Amazon Product API. I now published it as part of my new Amazon Tools project, that can be downloaded as complete class with examples here. It's licensed under Simplified BSD License.
/**
* signs the request Url for the Amazon API
* @param str pUrl unsigned Url
* @param str pSecretAccessKey it's a hash to sign the Url,
* you get that from the Amazon-Partner network
* together with your AccessKey
* @return signed Url
*/
function &signRequestUrl($pUrl,$pSecretAmazonHash){
// retrieve Parameter from urls
$arrUrlParts = parse_url($pUrl);
$vParams = $arrUrlParts['query'];
// parameters are separated by & so we put them in
// another array, in there are values like "aa=bb" "xx=yy"
$arrParams = explode('&',$vParams);
// loop and put pair/values in array
foreach($arrParams as $vPair){
// easy separating of the name/val by using explode
$arrPair = explode('=',$vPair);
$arrParamsSort[$arrPair[0]] = $arrPair[1];
}
// Timestamp needed if there is none present
$arrTemp = array_change_key_case($arrParamsSort,CASE_UPPER);
// format from amazon-docs
if (empty($arrTemp['TIMESTAMP'])){
$arrParamsSort['Timestamp'] = gmdate('Y-m-d\TH:i:s\Z');
}
// sort the array, needed to make the Url canonical
ksort($arrParamsSort);
// canonical means that the parameters are sorted
// so it's easier to check if urls are different
$vCanonicalString = '';
foreach ($arrParamsSort as $vKey => $vVal){
// rawurlencode => 5.3 should be RFC 3986 compliant
// for php versions below this should do the job
$vNewVal = str_replace('%7E','~', $vVal);
$vCanonicalString = $vCanonicalString.$vKey.'='.rawurlencode($vNewVal).'&';
}
// remove last &
$vCanonicalString = rtrim($vCanonicalString,'&');
// from he amazon docs
$vSignString = "GET\n".strtolower($arrUrlParts['host']).
"\n".$arrUrlParts['path']."\n".$vCanonicalString;
// generate the hash from the request
$vSignature = hash_hmac('sha256',$vSignString,$pSecretAmazonHash,true);
// and base64 encode it
$vSignature = rawurlencode(base64_encode($vSignature));
// rebuild the url with the signature
$vRet = $arrUrlParts['scheme']."://".$arrUrlParts['host'].
$arrUrlParts['path']."?".$vCanonicalString."&Signature=".$vSignature;
return $vRet;
}