Another weird case with AWS CloudFormation. I attempted to start an EC2 instance and for somewhat reason it failed and said it doesn't have ec2:RunInstances permission, but it does. After few checks, I found out that the cause is the IamInstanceProfile. If it is set, the error happens.

With clue from some online forum, I tried adding iam:PassRole permission for CloudFormation instead of the required ec2:RunInstances and it works!