SPF not working

Hi!

I am running Postfix and I have set this SPF record in my DNS hosting in "domain.com":

Code:
"v=spf1 include:<public_ip> ~all"
Where "public_ip" is my public IP.

I am running Postfix from inside a VM with its own internal IP.

The command issued is:

Code:
echo "Message body" | mail -s "Subject" name@gmail.com -aFrom:name@domain.com
I am able to send the e-mail to GMAIL. However, it flags the mail with a:

Code:
SPF: PERMERROR with IP <public_ip>
What am I doing wrong?

Thanks!