I have a different situation but with the same response.
Gmail is saying I'm missing PTR record but the IP to wich is reffering is the routable IP not the public one. So I asked my ISP to add a rDNS to that IP as well and guess what? Gmail says the same thing.
Now, I'm not some sort of a class A sys admin, but neither a mega-idiot, so, why the hell does Gmail need a PTR record to my routable IP? And much more, this happened two weeks ago all of a sudden. I did not changed anything, I didn't messed up with my courier setup, DKIM and SPF records are there untouched, just that I made an apt-get -y upgrade and it did in fact updated courier and postfix, but, of course, I compared the backup files main.cf and master.cf and nothing changed.... So it's not from the update.
Furthermore, to make it even harder, last week worked..... 50% of the emails went to gmail, rest of them returned. I have around 40 clients, 130 mailboxes, anti-spam filters like a maniac, and the last 3 years the email server worked with no problem whatsoever...
Help!!!! I'm loosing my mind in here.
PS: please don't ask me why I'm using apt under CentOS
...