That sounds like a problem with DigitalOcean’s DNS service unfortunately. Especially if our own DNS entries (your-app.fly.dev) work fine.
I’d recommend using another DNS provider. A summary search showed others have had the same issue, but there doesn’t seem to be a fix.
We like DNSimple for ourselves, if you’re looking for a recommendation.