I am trying to create a connection for "Invoke an HTTP Request" and trying to connect via on-premises data gateway:

I am not able to select the gateway because drop-down is grayed out.
It seems I should select a Subscription in the drop-down first but it does not contain any values nor cannot it be expanded.
I can see the data gateway up and running in Power Platform admin center:

Interestingly, some flows that were set up earlier that uses this on-premise data gateway are able to run so Power Automate definitely has knowledge about the data gateway and is able to use it.
I just cannot set up any more connections.
I have ensured that I have the usage rights on the data gateway.
Furthermore, the on-premise data gateway was upgraded to the newest version.
What is missing? Did MS change something?