Yahoo flagging mail as spam when using relay server

I'm using Postfix to relay mail from my site to my mail server. Mail is received properly at my Gmail and Hotmail accounts – only Yahoo is the problem. The Yahoo mail headers state:

Received-SPF: none
(mta1133.mail.mud.yahoo.com: domain of
xxxx@xxxxx.com does not designate
permitted sender hosts)

In contrast, the Gmail headers state:

Received-SPF: pass (google.com: domain
of xxxx@xxxxx.com designates
74.50.xxx.xxx as permitted sender) client-ip=74.50.xxx.xxx;

Reverse DNS is set up correctly, as is my SPF record and domainkeys/dkim (both domainkeys and dkim show pass(ok) in the Yahoo mail headers).

Does anyone have any suggestions as to what I can do to solve the Yahoo problem (short of contacting Yahoo, as this is a brand new mail server)?

Thanks