Sender Policy Framework (or SPF) is an email validation system designed to addressing source address spoofing. It allows administrators to specify which hosts are allowed to send email from a given domain by creating a specific DNS SPF record in the public DNS. Mail exchangers can then check that mail from a given domain is being sent by a host sanctioned by that domains administrators.

So, after setting up mail from Google apps you’re getting this error:
(IP addresses and domains have been changed to protect the innocent)

SMTP error from remote mail server after RCPT TO:<email@domain.com>:
host something.email.com [127.0.0.1]: 550 <email@domain.com>:
Recipient address rejected: undeliverable address:
host domain.com[127.0.0.1] said: 550-something.email.com [127.0.0.2] is currently not permitted to relay 550-through this server. Perhaps you have not logged into the pop/imap server 550-in the last 30 minutes or do not have SMTP Authentication turned on in your 550 email client. (in reply to RCPT TO command)

You check your DNS records and everything seems to be in order…
You’ve changed your cname for mail to point to Google: ghs.google.com
You’ve changed your MX records for your domain to point to Googles: aspmx.l.google.com etc
You’ve configured your server in Cpanel to act as a Remote Mail Exchanger

For Google to accept your mail server as a relay, you need to enter a line in your DNS zone:

yourdomain.com TXT v=spf1 include:_spf.google.com ~all

(Do not use the built in SPF in Cpanel, and you may need your host to enter this line for you)

A little info is here for Google Support
Background reading in SPF in Wikipedia is here