It turns out the intermediate and root CA were missing from the system's certificate stores. I used the solution from this SO post to check the certificate chain: https://stackoverflow.com/questions/28101140/get-chain-of-certificates-for-a-file-with-powershell. The last certificate listed in the list of certs must be included in the Trusted Root Certification Authorities store.
After including the necessary certificates, the AppLocker cache needs to be deleted (C:\Windows\System32\AppLocker\AppCache.dat) after which previously blocked apps who use those certs should run without issue.
It's interesting that the AppLocker logs omit the name of the application when the root CA of the signed package can't be found. It would be useful to include the name of the application and even go so far as include the reason the AppLocker rule failed e.g. <app name> was prevented from running. Signature was not trusted". It would also be useful if Test-AppLockerPolicy identified these issues since, in my case, it claimed the application was "Allowed".