We have a dedicated server and host our email via GoogleApps.

We've got an SPF record established
v=spf1 include:_spf.google.com ~all
We are getting a softFail response. There is one email network in particular we are having trouble sending email to and their IT reps claim it's because of this SPF issue.

Prefix Type Value PrefixDesc Description
+ include _spf.google.com Pass The specified domain is searched for an 'allow'.
~ all SoftFail Always matches. It goes at the end of your record.
Is there any suggestions as to how I can fix this SoftFail issue? Does it have something to do with a PTR record?