I ONLY use and recommend Hostgator and SEO Hosting and have not had problems with hundreds and hundreds and hundreds of WP installs so I'd not suggest changing host.
I would turn off the plugin and see what happens, then turn off any themes and use only one of the defaults and see what happens.
Also, if you turn off both and are still having problems contact Hostgator support. Go the email route, the chat line folks are good enough but if you need 'help' email is going to be best.
If the plugin is the issue then there are plenty of others to look at. Plugin compatibility is an ongoing issue with WordPress, no surprise really given all the jobs they do and the varied ways in which they do them. Wait till you are running a pack of 30 or so of the little buggers, it can be like herding cats after some WP updates.
