Codedeploy agent “The security token included in the request is invalid”

Today our CodeDeploy setup started failing for one of the instances with the following error:

The overall deployment failed because too many individual instances
failed deployment, too few healthy instances are available for
deployment, or some instances in your deployment group are
experiencing problems. (Error code: HEALTH_CONSTRAINTS)

Upon checking /var/log/aws/codedeploy-agent/codedeploy-agent.log on both servers, one of them has the following error:

2017-07-13 15:45:57 INFO [codedeploy-agent(10192)]: [Aws::CodeDeployCommand::Client 400 0.013838 0 retries] poll_host_command(host_identifier:"arn:aws:ec2:us-west-2:088736878764:instance/xxxx") Aws::CodeDeployCommand::Errors::UnrecognizedClientException The security token included in the request is invalid.

2017-07-13 15:45:57 ERROR [codedeploy-agent(10192)]: InstanceAgent::Plugins::CodeDeployPlugin::CommandPoller: Cannot reach InstanceService: Aws::CodeDeployCommand::Errors::UnrecognizedClientException - The security token included in the request is invalid.

How would one go about fixing this? I'm not sure what to start with.
The only change on this server was to set :max_revisions: 2 in codedeployagent.yml, restart codedeploy-agent and then delete (due to disk space constraints) an old revisions folder in /opt/codedeploy-agent/deployment-root/ which was dated to 2016.

I remember that manually deleting revisions (the ones starting with d-xxx) from an active revisions folder (the ones with the long hash id name) causes a big problem to CodeDeploy and the only solution is to recreate the deployment application. But this cannot be the case here, can it?