Over the irritating fact that you are forced to add a credit card to try free plan (say goodbye to lot of users), my cc is also refused (it has credit, it’s valid and I just bought from amazon without an issue).
Growing pains. You may want to email Fly (support@fly.io; ignore the auto-reply) with your credit card provider / location / other relevant information, so they may attempt to fix it?