Elasticbeanstalk: Failed to deploy application. Verify the permissions on the environment's service role.

I'm having trouble deploying to ElasticBeanstalk, it says:

Deployment completed, but with errors: Failed to deploy application. Failed to check health. Verify the permissions on the environment's service role and try again later. Permissions changes take up to two hours to propagate.

It's not at all clear what to do here.

I can see that the service role is Service role: arn:aws:iam::*:role/aws-elasticbeanstalk-service-role

I can see that the service role exists and appears to be correct.

It's not clear what the actual issue is or how to diagnose it further.