If your host changed your servers around, then perhaps your store is pointing to the wrong database server now?
Or maybe they have a cluster that's not operating properly and sometimes your customers see old out-of-date data and other customers see current data.