DId you change your firewall port forwarding, rules regarding SMTP and other settings if the internal mail server IP address changed?
Have you checked your firewall logs to see if it is dropping or even receiving SMTP traffic?
With your previous mail server did you employ another server for mail FILTERING. If so, is it forwarding the inbound e-mail to the new IP (if different than the old mail server)?
The FQDN used should not matter as long as the A and MX records match up.
- Tom