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