email - Google Apps e-mail being rejected from some domains

I'm migrating e-mail for my domains to Google Apps' e-mail. Most everything seems to work except e-mail sent to any user at (at least) sonic.net is rejected with a message of the form (where any-address has been substituted for my friend's address):

From: Mail Delivery Subsystem 
Date: March 11, 2010 10:04:48 AM PST
To: paul@pauljlucas.org
Subject: Delivery Status Notification (Failure)
Delivered-To: paul@pauljlucas.org
Received: by 10.229.194.26 with SMTP id dw26cs8717qcb; Thu, 11 Mar 2010 10:04:48 -0800 (PST)
Received: by 10.223.68.143 with SMTP id v15mr3841599fai.62.1268330688325; Thu, 11 Mar 2010 10:04:48 -0800 (PST)
Received: by 10.223.68.143 with SMTP id v15mr5119424fai.62; Thu, 11 Mar 2010  10:04:48 -0800 (PST)
Mime-Version: 1.0
Return-Path: <>

X-Failed-Recipients: any-address@sonic.net
Message-Id: <0015174beb0622a55804818a401a@google.com>
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

Delivery to the following recipient failed permanently:

    any-address@sonic.net

Technical details of permanent failure: 

Google tried to deliver your message, but it was rejected by the recipient domain.
We recommend contacting the other email provider for further information about the
cause of this error. The error that the other server returned was: 550 550 5.1.1
... No such user here (state 13).

And here are the headers from the message it bounces back:

Received: by 10.101.90.7 with SMTP id s7mr2515885anl.176.1267979929490;

       Sun, 07 Mar 2010 08:38:49 -0800 (PST)
Return-Path: 
Received: from [10.0.1.203] (adsl-76-201-171-194.dsl.pltn13.sbcglobal.net [76.201.171.194])
       by mx.google.com with ESMTPS id 4sm1046550yxd.70.2010.03.07.08.38.48
       (version=TLSv1/SSLv3 cipher=RC4-MD5);
       Sun, 07 Mar 2010 08:38:49 -0800 (PST)
From: "Paul J. Lucas" 
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: quoted-printable
Subject: Some fascinating subject

Date: Sun, 7 Mar 2010 08:38:46 -0800
References: <2B1416BF-ACA7-4B55-A8B5-A298543CE850@lucasmail.org>
To: any-address@sonic.net
Message-Id: <06536C2D-2402-4648-9BCB-99D41B36813F@pauljlucas.org>
Mime-Version: 1.0 (Apple Message framework v1077)
X-Mailer: Apple Mail (2.1077)

However, I am able to send mail to a user at sonic.net using my old e-mail account. Also, my company uses Google Apps for e-mail and I can send e-mail to a user at sonic.net from my company. The differences between my personal e-mail and my company's are:

• My company's domain has no SPF record whereas mine does.


• My company's domain has an A record whereas mine does not.

My SPF record initially was as prescribed by Google here.
However, this guy claims Google is wrong and gives a fix. I've tried it both ways with no difference.
My SPF record is currently:

v=spf1 mx include:aspmx.googlemail.com include:_spf.google.com ~all

As for the lack of an A record, you wouldn't think that a mail host would care about that so long as mx records are defined.

However, the funny thing is that if you look at the error message, why does Google state that the recipient's domain stated that there is "No such user here" for my address? That makes no sense. Of course there is no user having my address at sonic.net.

Also, I assume that I just discovered that I can't send mail to users at sonic.net by accident and that there are probably other domains I can't send e-mail to.

So... anybody have any idea what's going on? And how I can get mail to users at sonic.net?