...

I already have an SPF record which says: v=spf1 mx ~all, what's wrong with that?

LOTS. It doesn't specify a valid server. try this "v=spf1 a:fcx2.keithdiane.us include:_spf.google.com ~all" Dick