Could be the new IP you are on on your new server getting snagged as spam. could also be their setting in their usercp. sometimes during a server move things happen. have them check and ensure their settings are good, then maybe send them a test email from the ACP, and if they STILL dont get it start researching as to whether or not your IP is blacklisted...
use this site to check and see if your IP is blacklisted
http://www.mxtoolbox.com/blacklists.aspx