aws cdk The role with name cannot be found (Service: AmazonIdentityManagement; Status Code: 404; Error Code: NoSuchEntity)

Using the new version of the bootstrap stack I did

$ env CDK_NEW_BOOTSTRAP=1 npx cdk bootstrap \
  --cloudformation-execution-policies arn:aws:iam::aws:policy/AdministratorAccess \
  aws://<myAccountId>/<myRegion>

where <myAccountId> is my aws account id and <myRegion> is the region I'm in. However, this gives me an error saying:

CDKToolkit: creating CloudFormation changeset...
6:37:47 PM | UPDATE_FAILED        | AWS::IAM::Role        | CloudFormationExecutionRole
The role with name cdk-...-cfn-exec-role-<myAccountId>-<myRegion> cannot be found. (Service: AmazonIdentityManagement; Status Code: 404; Error Code: NoSuchEnti
ty; Request ID: ...)

It is telling me the role doesn't exist but shouldn't the role be created when I call bootstrap?

I'm using cdk version 1.59.0. In ~/.aws/credentials, default user has admin access. I also added

{
  "context": {
    "@aws-cdk/core:newStyleStackSynthesis": true
  }
}

to cdk.json.

Any suggestions would be much appreciated.

EDIT: The first deploy worked, but in the next deploy I get

 Could not assume role in target account (did you bootstrap the environment with the right '--trust's?): User: arn:aws:iam::<myAccountId>:user/testapp_cdk is not authorized to perform: sts:AssumeRole on resource: arn:aws:iam::<myAccountId>:role/cdk-...-deploy-role-<myAccountId>-<myRegion>

EDIT2: I tried using --trust argument:

env CDK_NEW_BOOTSTRAP=1 npx cdk bootstrap --trust <myAccountId> --cloudformation-execution-policies arn:aws:iam::aws:policy/AdministratorAccess aws://<myAccountId>/<myRegion>

This also gave me an error saying

The role with name cdk-...-cfn-exec-role-<myAccountId>-<myRegion> cannot be found. (Service: AmazonIdentityManagement; Status Code: 404; Error code: NoSuchEntity; Request Id: ...)