GoogleApp softfail

Hello,

I have some hosts that use GoogleApp in the same linode. But all emails that my VPS sends gmail marks it as a "softfail".

As you can see, I am trying to send from host

> Delivered-To: XXX@gmail.com

Received: by 10.236.106.101 with SMTP id l65cs221174yhg;

Wed, 10 Aug 2011 10:21:15 -0700 (PDT)

Received: from mr.google.com ([10.42.19.133])

by 10.42.19.133 with SMTP id c5mr9365870icb.336.1312996875114 (num_hops = 1);

Wed, 10 Aug 2011 10:21:15 -0700 (PDT)

Received: by 10.42.19.133 with SMTP id c5mr7504099icb.336.1312996874823;

Wed, 10 Aug 2011 10:21:14 -0700 (PDT)

Return-Path: XYZ.com.br>

Received: from spire.com.br (li259-67.members.linode.com [173.255.249.67])

by mx.google.com with ESMTP id a1si1588856ibl.129.2011.08.10.10.21.13;

Wed, 10 Aug 2011 10:21:13 -0700 (PDT)

Received-SPF: softfail (google.com: domain of transitioning XXX@XYZ.com.br does not designate 173.255.249.67 as permitted sender) client-ip=173.255.249.67;

Authentication-Results: mx.google.com; spf=softfail (google.com: domain of transitioning XXXX@XYZ.com.br does not designate 173.255.249.67 as permitted sender) smtp.mail=XXXX@XYZ.com.br

Received: from spire.com.br (spire.com.br [127.0.0.1])

by spire.com.br (Postfix) with ESMTP id 44C8C48E81

for <XXX@gmail.com>; Wed, 10 Aug 2011 14:21:13 -0300 (BRT)

Content-Type: text/html; charset="us-ascii"

MIME-Version: 1.0

Content-Transfer-Encoding: 8bit

I just configured TXT Records for spire.com.br and XYZ.com.br with:

"v=spf1 a mx include:_spf.google.com ~all"

Can anyone help me?