Hm… The classic next thing to try is --depot=false --buildkit=false --recreate-builder.
You can also move the builder, in case it’s a network glitch of some kind:
https://community.fly.io/t/region-cannot-host-your-machine-fra/23071/31
(The builder region doesn’t necessarily follow your app around, which many people find non-intuitive.)
Frankfurt is one of the regions that has multiple datacenters, if I remember correctly, so there may be a problem with a subset not being able to talk to the rest of the Fly.io fleet…