Have you checked that the string you construct for the signature is actually as the documentation says?

You interpolate %params into the string, but you don't specify the order of the keys.

My hint is to print out the string before you compute the mac for it, and manually compare the string with what the documentation says.