A couple of thoughts:
Maybe try:
fly auth login
… to double-check you are authenticated, to rule that out as an issue.
Then I think you can add a log level so show some more details. I suspect Fly may need those extra debug lines to try and see what’s happening:
LOG_LEVEL=debug fly deploy
If you can paste in that output (removing anything you don’t want revealed, like your app name) here, that will help diagnose it.