Please let us know what error message you're getting on the 'bounce back'. It could be due to reverse DNS no longer matching the new IP - many email servers check reverse DNS entries upon receipt of new emails as a way to block spammers. I think this is the most likely problem here....
Regards,
Ady