Sorry to hear that, 
… Usually, fly deploy --depot=false works around this, although there are some caveats as noted upthread.
Another technique that sometimes helps is to move the builder over to a different region:
https://community.fly.io/t/region-cannot-host-your-machine-fra/23071/31
(These days, you might also need --recreate-builder.)