Its a very common error and you can go crazy during troubleshooting this error because everything seem perfect and working. Microsoft has provided different solutions of this error and most of them are good to solve this problem but sometimes you feel unlucky because this error is not specific to web services and it can appear if your public folder in IIS server is not pointed towards the right location. I got this error on one of my Exchange server and it took more than 12 hours to figure out and resolve the error. This error mostly appear after a sudden restart of your e-mail server when one of the required service did not start properly and crashes at startup. Windows mostly shows an error at login that one of the service did not start properly.
Microsoft exchange information store is a service for Microsoft Exchange server to display public folder in Outlook Web Access so that one can use exchange server over the web. At startup due to windows problem or any other problem this services crashes and did not start properly. The Startup Type of this service is automatic but still does not start automatically at startup. You just need to start this service and everything will start like charm. To start the service go to run and enter the following command services.msc. Today one of my exchange server was again showing this error and it took only 10 minutes to figure out and solve the problem. There may be other causes of this problem, for more information to troubleshoot this error please visit the Microsoft knowledge base here or here.