You may need to do this on the server and the clients.
If your MX record has changed with your new situation, you will have to change it. It will not do this by itself.
And for a better understanding, you will have to clearly explain what has changed where: In your local network, at the hosting service, etc.
A hosting service cannot be in control of your LAN traffic, so take that into consideration. If you expect to reach the mailserver by going out over the internet then bouncing back to hit your Public email address, the mailserver will have to be able to allow your users access to their accounts or whatever over the public side (which I would not really advise).
So, why not tell us what happens when a user attempts to use the mailserver - what errors? Have you traced packets with Wireshark or similar to see what is happening?
Or is this supposed to be a mailserver provided by the hosting company? What are they providing for you? Just a domain name? More than that?
You can try looking up your domain name with a service like http://www.robtex.com/ , and see what the MX records listed show. You can try http://www.dnscog.com/ for a bunch of DNS analysis.
For further posts here, you will need to be a bit more clear as to how users used to connect to the mailserver (route, etc.), and how you expect to connect to the mailserver now (route, resolution, etc.).