GPO Published Programs suddenly failing with "Fatal error during installation."

We've made a number of programs available to our users by publishing them via GPO. This has worked just fine for years. If a non-admin wants a program, they go to Programs and Features, click "Install a program from the network", select the program from the list and then click "Install".

Today I went to do this and immediately got the message "Fatal error during installation." This happens for any program in the list, many of which have not been modified in years.

I can't find any errors logged in the Event Viewer. Running Process Monitor reveals that "msiexec" is never called.

I've checked all the file, folder and share permissions for where the msi files are located and verified that both the computer accounts and the user accounts have read+execute access. I even used psexec to log in remotely as SYSTEM and successfully installed one of the programs using msiexec manually.

I'm at my whit's end trying to diagnose this. Does anyone have any suggestions of anywhere else to look for issues?