Creating new Lambda application in a fresh account gives me "Unable to fetch parameters" error.

I encountered this error in another account, so I created a new one to troubleshoot. Same situation:

• Go to Lambda console
• Create new application
• Select the serverless / dynamodb template
• Go through setup, connect to a github repo, etc
• During the last phase of setup, it gives the following error:

Unable to fetch parameters [/cdk-bootstrap/hnb659fds/version] from parameter store for this account. (Service: AmazonCloudFormation; Status Code: 400; Error Code: ValidationError; Request ID: d341e6cc-1ae1-4df8-99b9-922aa6a5c8ea; Proxy: null)