I ran into a problem where a stack would not build on AWS with the above error message. When you tried to create the stack it would simply hang and wait for 40 minutes or so, and then rollback.
The problem turned out to be a parameter of type:
AWS::SSM::Parameter::NameAnd the IAM role building the stack did not have appropriate SSM permissions to determine whether that role existed or not. Specifically it did not have ssm:GetParameter.