Obviously Gmail uses Sender-ID and DKIM to verify every email. That is why you need to modify DNS records for your domain using txt record. Here is a tutorial how to do that openspf.org.
You can build your txt records using the wizard and add them. You need something like:
record for domain.com in txt: v=spf1 a mx ~all
record for the mail server mail.domain.com in txt: v=spf1 a -all