User is not authorized to perform: cloudformation:CreateChangeSet

Based on the error message and your testing, this appears to be a permissions issue with the AWS Serverless Application Model (SAM) transformation. Even though you've verified that your users have the necessary CloudFormation permissions and you've tested with AdministratorAccess and even the root user, there seems to be an explicit deny somewhere that's preventing the CreateChangeSet operation specifically on the Serverless transform resource.

The error is specifically related to the Serverless transform (arn:aws:cloudformation:us-east-2:aws:transform/Serverless::2016-10-31) rather than a regular CloudFormation stack, which explains why your regular CloudFormation deployments work fine.

Since you mentioned this was working last week but is failing this week, and you've already verified that there are no Organization SCPs blocking access, there might have been a change in how permissions are evaluated for the Serverless transform, or there could be a temporary service issue.

Here are some troubleshooting steps to consider:

1. Check for any explicit deny statements in your IAM policies that might be targeting CloudFormation transforms specifically.

2. Ensure that your IAM policies include permissions not just for CloudFormation actions but also for the specific transform resource. You might need to add explicit permissions for the Serverless transform.

3. Try adding the following to your IAM policy:

{
"Effect": "Allow",
"Action": "cloudformation:CreateChangeSet",
"Resource": "arn:aws:cloudformation:*:aws:transform/Serverless-*"
}

4. If you're using AWS SAM CLI, ensure it's updated to the latest version, as there might have been changes in how it interacts with the CloudFormation service.

5. Since you mentioned it was working last week, consider opening a support case with AWS if none of the above steps resolve the issue, as there might be a service-side change or issue.

Remember that in IAM, an explicit deny always takes precedence over an allow permission, so even with AdministratorAccess, if there's a specific deny for this resource, it will block the operation.
Sources
(AccessDenied) when calling the CreateChangeSet operation: | AWS re:Post
Step 3: Limit the CodeDeploy user's permissions - AWS CodeDeploy