can you export the cuj job run log for the past couple runs, your patching job run log and get all the appserver logs that cover the time of the issue ?
you may also want to go ahead and open a support case.
I did log a support case also and we found the following line in the cuj job run log:
[CatalogUpdate] Error while add/update patch in depot: bulletin : MSAF-024, , Error: Access Denied WindowsSoftware.Modify on MSAF-024
So, the problem was a permission issue one of the Windows bulletin objects. We fixed the permission issue and all good now.