It could be related to a blocked website actually. If their ISP is dns hijacking to block a website the browser certificate authority will report it as untrustworthy/insecure. Similarly if an authentication server is down, a certificate expires, or they just use http instead of https this could lead to website issues like this. Of course it could be a client-side issue as well like incorrect date/time, antivirus complications, etc.
They haven't really given us enough info to fully troubleshoot but based on it affecting a lot of sites and being alleviated by a VPN connection - if they haven't recently had any changes (new programs, new network, etc) I'd wait a day and see if it's just an ISP hiccup.