boto responds: AWS was not able to validate the provided access credentials
Had a similar issue and decided to post it as an answer given that this may help others (coming here from Google):
Make sure the time on your machine is set correctly.
My machine's time was running just ~8 minutes ahead of the real time and this was causing 401 exactly as above.
If you are on Linux you can do the following to synchronize:
sudo ntpdate us.pool.ntp.org
Man oh man. There is a $HOME/.boto file that saves your old authentication values. Most of a day lost due to this !!
cat ~/.boto
[Credentials]
aws_access_key_id=MY*OLD*ACCESS*KEY
aws_secret_access_key=MY*OLD_SECRET*ACCESS*KEY