Posting the solution in case anyone else finds it helpful.
The cause ended up being a duplicate thumbprint in the Strong Name Mapping GPO tuple. For whatever reason the duplicate did not cause an issue in processing the tuples for over a month (since the last update to that GPO), and applying the cumulative update caused the processing of the tuples to fail. Failure is technically the correct response in that situation, since documentation explicitly states that each tuple must have a unique thumbprint. However, the delayed failure response caused considerable troubleshooting delays as it suggested a recent change or event had caused the authentication issues.
The key factor in determining the source was a Kerberos log on our domain controller.
Event Viewer | Applications and Services Log> Microsoft> Windows> Kerberos-Key-Distribution-Center: Operational
The operational log contained Event ID 313, which is sparse on information. It indicates that there is an invalid strong name match policy. It also includes a bit at the bottom reading: "Faulting Line: #". The 'Faulting Line' refers to the Strong Name Mapping GPO tuple list, where the # in the log indicates which line was considered the faulting line.
Regarding the reply I got:
The "SID extension (1.3.6.1.4.1.311.25.2)" is not relevant since we do not generate our certificate requests using Microsoft CAs.
Thank you for attempting to answer the question though.