Hi, Julien. We cannot troubleshoot this particular issue over the forum posts, you need to open a support case with this issue and do a live webex with one of our engineers to determine the root cause. Typically, it is caused by various problems with root certificates on the backup server machine. We've seen it before but frankly, it's not a very common problem, so I am quite puzzled as to why all your clients experience it.
Anyway, as soon as our support helps you fix the certificate issue, you will be able to install all updates without having to contact support.