office 365 – SharePoint Online Open in Explorer Access Denied

My organization rolled out Single Sign on with Office 365 a couple of months ago. Since the roll-out, several users (most of them on Windows 7) have had this error message:

{path} is not accessible. You might not have permission to use this network resource. Contact the administrator of this server to find out if you have access permissions.

Access Denied. Before opening files in this location, you must first add the web site to your trusted sites list, browse to the web site, and select the option to login automatically.

enter image description here

The SharePoint site is already in trusted sites. I’ve also tried setting the Webclient service to automatic start and it fixes it temporarily but it eventually comes back.

What can I do to resolve this?