Assuming your Exchange server is configured correctly(I assume the domain names not changed, so it should stay the same), the DNS record of external network may not have updated their DNS record.
The other possibility is that the routing to your Exchange server is on one-to-one-NAT, so you need to update the IP mapping for it to work.
A less common possibility (let's hope this not be the case) is that the new ISP does not allow inbound SMTP port. This will usually occur if you rent an office in residential area, and you accidentally signed up for a "not-for-work" plan.
Try doing "nslookup" for your domain and look at the MX record setting from a client that known to unable send you email to verify if this is your case. If it's not that case, try take a look at their SMTP server log and see if there is some hint on what happened.
======
Usually before moving email servers, we'll set the TTL of DNS record to low value (say, 15 minutes) and restore the value after done with transition . Since most mail server will retry after 5, 15 then 30 minutes when unable to contact destination mail server, this will allow you make the change with minimal disruption to service. Also, we'll use DNS View feature to setup temporary updated records to test machines to make sure the new mail server works correctly before actual act of moving. (Always good to have 2 days to a week of overlapping times on both ISP service contracts)