DNS changes (like those you made to the
MX records) can take up to 3 days to fully propagate. If it's been more than 3 days, then the problem above is likely being caused by your old email provider still being configured to pickup mail on your example.com
domain. Essentially what is happening is that mail is sent from a server on your old email provider's network makes its way to your old email provider's mail servers. Instead of checking
DNS and routing the mail to our servers (where the mail should go), your old email provider's servers are simply checking their configuration for email on the
domain example.com, and then delivering mail for that
domain to their mail servers.
To correct this problem, simply ask your old email provider to completely remove all references to example.com in their mail and DNS servers.