Just started getting this error today when trying to submit a fulfillment Free Shipping orders to Amazon through the mobile app.
Shipping method invalid for this fulfillment service
The order qualifies for Free Shipping, but is also marked as Standard Shipping in the Amazon fulfillment options. Normal non-free orders submit fulfillment fine through Amazon as Standard Shipping.
This is a new error since we've been clicking those fulfill buttons for a long time.
I wonder if it would work if you made 2 methods called Standard Shipping.
The way I do it for Amazon FBA is with 2 Standard Shipping methods, one regular and one qualifier for free shipping, and it will show accordingly on the checkout (maybe it will function the same with the app-way you're doing it).
Here's how it shows up if they have over $50 in cart (qualify for free shipping):
And if they have < $50: