Check that your credentials are correct. For example, if you are using gsutil, check that the credentials stored in your .boto file are accurate.
Assuming you are using the correct credentials, are your requests being routed through a proxy, using HTTP (instead of HTTPS)? If so, check whether your proxy is configured to remove the Authorization header from such requests. If so, make sure you are using HTTPS instead of HTTP for your requests.