I just went through the DNS change from HELL back in March for the website I adminster for my day job. It can take up to 72 hours for DNS to propagate, and in the meantime, you can have issues where it will work and break.
If your hosting company changed, most likely your email settings and/or login or server info has changed. Make sure that's correct first. It's the easiest problem to resolve and usually the culprit.
If you are calling and complaining about service interruption and it hasn't been 72 hours, expect no one to really care about helping you. In my case I *knew* something was set up wrong - I had a strong gut feeling, I've set up a lot of domains. I had to complain for a week before I got it resolved, and guess what, it was the problem I thought it was - my new host didn't configure the DNS correctly. I was routed back and forth from two hosting companies, the registrar, and my local ISP, before the problem was finally isolated.
Few things worth knowing:
If you are on a PC, you can go into the command line and refresh your DNS. This sometimes worked and allowed me to get my site to load/email to download. Click on Start ->Run and type in CMD then "ipconfig /flushdns" (minus the quotes) I'm sure there's a way to do it on a mac, but I'm allergic to macs.
If you are connecting to the internet via a router, your router may by default be connecting to a DNS server other than your
ISPs. If you don't know how to access your router settings, your ISP tech support can probably assist you. In my case, I found out the old 2wire router at my office was connecting to some weird DNS server by default and not the ISP's. It turned out to NOT be the ultimate problem, but you want to make sure you are using a reputable DNS server.
OpenDNS.com is a site that offers free DNS. You can use it
to check if your new DNS is populating. If you see it coming up there and it's still not coming up locally and it's been 72 hours, get on the phone and start yelling until you get someone with a pulse (and brain) on the line. (OpenDNS is actually pretty cool in its own right, it keeps track of annoying phising and portal sites, so if you miss type amazon.com it will just re-route you rather than going to a portal or getting a nice serving of malware from some malicious site. It also has some site blocking that parents might be interested in.)
If it's just mail related, and you are SURE your mail settings (including port settings) are correct, there may be problems with your
MX records.
I used
this site a lot to see what my DNS records were saying. One of the reports there helped me finally prove to my new host that there was a problem.
GOOD LUCK. I know exactly how frustrating this is! I could write a book on it!