We had this issue when we moved from staging to production. Worked fine on staging, but not on production.
It ended up the clock on one of our production servers was 6 minutes behind. This caused the expiration to error out. Immediately we increased the expiration, and ultimately set the proper time on the server.
This resolved all issues relating to the following error:
401 Error - Your authentication has expired. Re-send your authentication and try again. For more information on signed authentication, see: http://apiwiki.moz.com/signed-authentication