There may be times when your email service provider may require you to validate your domain with and SPF record. Typically their systems are expecting to see their EXACT SPF record in your SPF record, and they are not doing deep validation. 

You have two options here:

1. Contact their support and let them know that you have a flattened SPF and you need manual validation or. 

2. Add the required SPF record to the TOP level of your SPF along side your include. 

It would look something like this:

current record: "v=spf1 ~all"

record to validate: "v=spf1 include:their.domain ~all" 

As soon as it validates make sure you have their include in your autospf record, and then revert back to the record with just the record. 

This is an example from Zoho Email failing to validate