I've renamed your .htaccess file to .htaccess.bak, which resolved the problem. There is something inside the .htaccess that is either not formatted properly, or is otherwise wrong, although I've not got enough experience working with .htaccess files to be able to tell what exactly.
This didn't have anything to do with the hosting service however - switching hosts wouldn't fix a .htaccess that isn't formatted properly.