Strange Email Issue with new domain

[ace2109]

Hi Guys,
In a nut shell we host around 15 domains on our dedicated server and all have email that is working fine. We added a new domain and email service for a new client and now they cannot send email to some outside domains.

This new client was running a local exchange server, which wasn't really setup all that well. We moved them over to our setup and as i have said above they cant send to certain domains that they could have done before.

I contacted our servers host who looked into the problem and they have said its a greylisting problem with the receiver however I dont understand how this can happen if they were able to send mail before the change?

Domain with email problems - www.niyf.org

This is the bounce back email they are receiving:

This is the mail system at host server88-208-192-201.live-servers.net.

I'm sorry to have to inform you that your message could not
be delivered to one or more recipients. It's attached below.

For further assistance, please send mail to <postmaster>

If you do so, please include this problem report. You can
delete your own text from the attached returned message.

The mail system

<[email protected]>: host bytes.org[79.125.4.125] said: 554 Blocked by SPF ()
(in reply to end of DATA command)