Do you have an SPF record setup? If not, then it is their end, they are being too restrictive.
If you have an SPF record setup for your domain, check you are referencing your sending IP or hostname.
See SPF txt record by typing at command prompt:
nslookup -q=txt yourdomain.com
Shaun