You've probably done these steps, but here it is:
Do you have access to the panel here? You can also try webmail.EXAMPLE.com and see if you can log in.
The good news is that you should be receiving your mail that's forwarded to Gmail. If that's the case, then you use Gmail to send mail from your domain as well. Go to Gmail and click Settings and then the Accounts tab. You can add your business account in the "Send Mail As" section.