CGI Error in archive/category links: “CGI application misbehaved…”

I am trying to get WordPress up and running on a new server (I have successfully installed it twice on an old server). Everything is working fine, except for the category and archives links. Whenever I click on either of these, it returns a page that says simply:

“CGI Error

The specified CGI application misbehaved by not returning a complete set of HTTP headers.”

I have already contacted my host, and they have done several checks for issues on their end and said that everything should be working fine.

Anyone know what is going wrong here?

Thanks in advance!