Why is Google rejecting mails forwarded from my Postfix server?

I've set up Postfix and created an alias that maps to a gmail account. When I mail from one of my own (google mail) accounts, it goes through, but if someone from the outside mails me, Google won't accept the mail from my server. The logs something contains this:

Aug 20 13:47:09 Ubuntu-1204-precise-64-minimal postfix/smtpd[8249]: connect from mailout.example.com[1.1.1.1]
Aug 20 13:47:09 Ubuntu-1204-precise-64-minimal postfix/smtpd[8249]: DB399E3318: client=mailout.example.com[1.1.1.1]
Aug 20 13:47:09 Ubuntu-1204-precise-64-minimal postfix/cleanup[8253]: DB399E3318: message-id=<015e01ce9d9a$f988a750$ec99f5f0$@dk>
Aug 20 13:47:09 Ubuntu-1204-precise-64-minimal postfix/qmgr[8230]: DB399E3318: from=<[email protected]>, size=3813, nrcpt=1 (queue active)
Aug 20 13:47:09 Ubuntu-1204-precise-64-minimal postfix/smtpd[8249]: disconnect from mailout.example.com[1.1.1.1]
Aug 20 13:47:10 Ubuntu-1204-precise-64-minimal postfix/smtp[8255]: DB399E3318: to=<[email protected]>, orig_to=<[email protected]>, relay=gmail-smtp-in.l.google.com[2a00:1450:4010:c04::1b]:25, delay=1.1, delays=0.22/0/0.14/0.76, dsn=5.7.1, status=bounced (host gmail-smtp-in.l.google.com[2a00:1450:4010:c04::1b] said: 550-5.7.1 [2a01:4f8:d12:11c2::2      16] The sender does not meet basic ipv6 550-5.7.1 sending guidelines of authentication and rdns resolution of sending 550-5.7.1 ip. Please review 550 5.7.1 https://support.google.com/mail/answer/81126for more information. qh9si1111170lbb.172 - gsmtp (in reply to end of DATA command))

The relevant part seems to be:

The sender does not meet basic ipv6 550-5.7.1 sending guidelines of authentication and rdns resolution of sending 550-5.7.1 ip. Please review 550 5.7.1 https://support.google.com/mail/answer/81126 for more information.

Any idea how I can solve this?

Edit

On the mails that do come through, I find the following headers:

Received-SPF: neutral (google.com: 1.1.1.1 is neither permitted nor denied by best guess record for domain of [email protected]) client-ip=1.1.1.1;
Authentication-Results: mx.google.com;
       spf=neutral (google.com: 1.1.1.1 is neither permitted nor denied by best guess record for domain of [email protected]) [email protected]

Now, the curious thing is that it appears that Google is evaluating my server against the SPF of the original sender. This is a third party, so I can't control their SPF. If I'm interpreting this correctly, Google thinks that my server is the origin of the message. Is this perhaps the crux of the problem?

Edit 2

It looks like I have the same problem as this: Why is SPF being validated against my mail server's IP instead of sender's IP?

Edit 3

So I've fixed the spf issue by installing pfix-srs and setting an spf record for my mail server. I followed this guide (Had to install some packages manually, since they aren't available for Ubuntu): http://blog.phusion.nl/2012/09/10/mail-in-2012-from-an-admins-perspective/

This appears to solve the spf issue (The mails now pass spf), but alas, mail is still getting dropped from some senders. I'm now trying to set the rdns entry and see if it resolves. I'll post back here once I know.

Edit 4

It worked. In summary, what I did to resolve this was:

• Install pfix-srs.
• Create an spf record for my mail servers domain, allowing my ip4 and ip6 to send. (E.g. v=spf1 ip4:1.1.1.1 ip6:abcd:abc:123:4567::8 ~all)
• Create an rdns entry for my mail severs domain, pointing to its IP.

The link that Google provides explains it very well. You should go through the list of requirements that Google lists there and check if you satisfy each of them, if not then fix that.

I think the most basic ones are these:

• Reverse DNS (Forward and Reverse lookup of your DNS and IP have to match)
• DKIM (DomainKeys Identified Mail http://www.dkim.org/)
• SPF (Sender Policy Framework http://www.openspf.org/)

If you satisfy these three requirements you should at least get accepted. The next step is to avoid the Spam folder, which might be a little more difficult. For a big part it depends on if users mark your email as spam, plus a few other details that are described in Google's support link https://support.google.com/mail/answer/81126.