Although curious who the host is ... who is the host?
... the hosting (at least right now, at this first stage of troubleshooting) is probably NOT the issue, if what you say is all accurate.
The redirects may very well be the issue.
Hopefully the redirects didn't also involve another domain (which you don't own).
The easiest way to see the requests (therefore getting 404 issues) is to look at the server analytics (not Google Analytics, but in the hosting control panel, hopefully either cPanel or Plesk), as well as using Google Webmaster Tools. See if any non-existent pages are being requested, getting 404 errors.
That's the first step.