Is there a .htaccess file that's changing the 404 page? How about a setting in their control panel? I'm not familiar with Hostgator's service but those are the only two options I can think of.
You can manage error pages (400,401,403,404,500..) from cPanel. Look for Error pages button in cPanel.
Both using the cPanel or redirecting in .htacess with mod_rewrite or ErrorDocument 404, will work with HostGator.
google "hostgator custom error pages" they have a short video that will explain it easily. I would give you the URL if I could...
It is very simple login to your FTP account of the domain, in th root folder you will file some HTML files with name 404.shtml 501.shtml etc. Remove them and replace them with your own.. that is it.