You have just created a Google Apps account and you have made all the changes to your MX records in DNS - everything is looking good - you give it 8 or so hours and you can see mail is flowing into your mailbox, however when you send mail you get bounce backs with strange SPF failure messages.
The above scenario, thankfully, has a simple fix: add or modify your SPF record. The example below is one that was fixed recently:
"v=spf1 +ip4:18.104.22.168 +a +mx -all"
To translate this:
v=spf1: SPF version 1
+ip4:22.214.171.124: Allow this IP version 4 address to send mail for this domain
+a: Allow any A record associated with the domain to send mail on behalf of the domain
+mx: Allow any MX records associated with the domain to send mail.
-all: Fail all other IPs trying to send mail for the domain.
We need to modify this line to read:
"v=spf1 +ip4:126.96.36.199 +a +mx include:_spf.google.com ~all"
Allows google mail servers to send for your domain.
~all: Soft fail - allow the mail through - but issue a warning.
Once this DNS change has propagated - your email will work without an issue.