Quoting Brian E. Lavender (brian@brie.com):

I fixed the dns entry for the SPF for the mail server and I also put in a reverse dns for it. I think it might work better now. :-)

:r! dig -t txt bigbrie.com +short "v=spf1 a mx ptr ~all"

You might be able to optimise that. I _used_ to have one that was that convoluted, but then realised that I could greatly reduce the amount of traffic required, because all outbound SMTP originated from one IP, and the least-convoluted, fastest-performance way of stating that in SPF RRs was just to cite the IP.

Looks to me (I could be wrong) that all of your outbound mail originates at IP 173.228.81.235, mail.bigbrie.com . So, you could have:

"v=spf1 ip4:173.228.81.235 -all"

Note: I subbed in '-' where you had '~'. If you're certain where your SMTP will be originating, it's in your interest to avoid the wishy-washy '~' operator.