I’m seeing the exact same error (also trying fly for the first time, attempting to deploy a phoenix app).
EDIT: I was able to solve this issue in my project by replacing the base image in the dockerfile with hexpm/elixir:1.14.0-erlang-25.1-debian-bullseye-20220801-slim