Hey @andig and @trevorm, it sounds like you may be running into the Buildkit issue described in this thread:
Images built using buildkit v 0.10.0 return a 404 error when we try to pull the image from docker.io, or from our registry. That post describes a work around to force buildkit to use an older version when building an image. Since you’re using a prebuilt public image that won’t necessarily help in this case.
As you’ve found out already, running fly deploy with the --local-only flag will work, because this uses your local docker daemon. If a local build isn’t an option for you, you can try downloading their public dockerfile and using fly launch to generate a fly.toml and build the image.
If you don’t have an active remote builder on your org we automatically create one during the fly deploy process. Since your deploy is failing before we create the builder, you won’t see it listed.