If you look at the response headers for a page, you can see that gzip is enabled. Simply put your URL in below, and you'll see the value of gzip for content-encoding:
web-sniffer.net/
There is a setting at the top which says "Accept Gzip", you must leave that enabled. That's a message sent from your browser to the server saying that you (the user) are capable of receiving GZip'ed content. The server then checks this setting, and if it's capable of GZip'ing the output, and then sends it encoded if both are true. Since it is being zipped, that means that something is zipping the contents.
Both the server are capable of zipping, and there are extensions in Joomla that can zip the contents (certain 'optimization' components/plugins can do this, as well as Joomla itself). I didn't see anything within Joomla that should be GZip'ing, which is why I believe it's your server.
Again, this may be a red-herring and not the cause, but everything I've read about the error you mention is that it's an encoding issue (which is what gzip does, it encodes the page a specific way). Gzip encoding can fail for multiple reasons. It expects a well formed HTML page (<html><head></head><body></body></html>), nothing to be sent before the response headers, and a few other things that are required. None of those seem like problems on your page, but unfortunately, this is the best solution I have to at least narrow down the problem.
Hopefully this helps you talk to your server provider and get a better answer. Please keep us posted as to what you find, and best of luck!