I'm getting the following in my mail logs on my app server:
550-5.7.1 [67.23.15.78] The IP you're using to send mail is not authorized to 550-5.7.1 send email directly to our servers. Please use the SMTP relay at your 550-5.7.1 service provider instead. Learn more at 550 5.7.1 http://support.google.com/mail/bin/answer.py?answer=10336
I've checked and the IP is not listed on any PBL/SBL/etc that I know of. The domain name in the FROM: email address is a CNAME to our app server's primary domain (djangostage.farstarserver.com). We have a PTR record for the server's IP, so reverse DNS resolves to the same domain (djangostage.farstarserver.com). We also have the following SPF record set up for the domain to allow our vhost domains on that server to send email under their own domains:
"v=spf1 a a:django.farstarserver.com -all"
Any ideas why Google is blocking our server?
Did you try clicking on the link in your question? It explains the situation rather nicely.
In addition to being blocked by Gmail, your IP is listed in the SpamHaus PBL. The same range is probably listed in similar DNSBLs run by other organisations. If you want to reliably send mail from this IP address, you will have to contact all of them.
SpamHaus suggest you read the RackSpace AUP before requesting removal. I would recommend finding a different IP to send mail from.
Talk to Slicehost/Rackspace. Use their SMTP relay or upgrade your package to one that is allowed to send mail.
Note that it is practically impossible to send email from an EC2 IP address too. That's why Amazon run SES.