Try going to http://whois.sc/Yourwebsite.com , replace Yourwebsite.com with your website and you'll find information on the domain, where it is registered so on to look into it further.
█•CirtexHosting•Providing Affordable and Quality Web Hosting & Reseller Hosting since 2003 █•LINUX based cPANEL/WHM Shared and Reseller Web Hosting with Fantastico █•HostV VPS•Premium Virtual Private Servers & Dedicated Servers powered by cPanel/WHM █•We transfer your sites over quickly!•I eat penguins for breakfast ...
1. Find the domain registar by running a whois.
2. Try to get access to the domain. Contact the registar and follow thier recommendation.
3. Get a new hosting account and set up the site from backup(which I believe you have)
4. Change the name servers at registrar and point the domain to new host.
From what I understand your provider changed the DNS. So the first things to do after making sure your hosting account is still up to date (paid and working) is to ask them which are the new DNS servers you need to configure on your domain.
Then it would be to update the domain with the new DNS servers. You do know where you registered the domain right?